一图扫描介绍图的扫描是对节点的访问。 图中有很多节点，如何穿越这些节点需要特定的策略，一般有两种访问策略。
1深度优先遍历
2广度优先遍历
二深度优先扫描基本思想图的深度优先搜索(Depth First Search )，简称DFS。
1深度优先遍历从初始访问节点出发，初始访问节点可以具有多个相邻节点，深度优先遍历的策略是首先访问第一个相邻节点，然后以所访问的相邻节点作为初始节点访问其第一个相邻节点。 这可以理解为每次访问当前节点后，首先访问当前节点的第一个相邻节点。
2该接入策略优先纵向挖掘，而不是横向访问一个节点上的所有相邻节点。
3深度优先搜索是一个递归过程。
三深度优先遍历算法的步骤1访问初始节点v，标记节点v已访问。
寻找2节点v的第一个相邻节点w。
如果3w存在则继续4，如果w不存在则返回步骤1，从v的下一个节点继续。
如果4w未被访问，则对w执行深度优先的循环递归(即，将w视为另一v，执行步骤1、2和3 )。
寻找5节点v的w邻接节点的下一个邻接节点，进入步骤3。
实战1中要求以深度优先搜索下图，从a开始扫描。
2思维分析
3代码import java.util.ArrayList； import java.util.Arrays； import java.util.LinkedList；/* * @ class name : graph * @ description :图* @ date :2021/3/28 * @ author : cak in */public class graph {/2 } 表示//边数的private int numOfEdges； //指示某个节点是否已访问private boolean [ ] is visited/* *功能说明：图中的擦拭* * @param args命令行* @ authorcakin * @ date 2021/3 args ) /顶点string //String Vertexs[]={'1'、'2'、'3'、'4'、'5'、'6'、'7'、'8'}； //节点的个数int n=Vertexs.length； //图对象graphgraph=newgraph(n )； //循环的附加顶点for(stringVertex:Vertexs ) graph.insertVertex ) Vertex )； //添加边graph.insert edge (0，1，1 )； //a-b graph.insert edge (0，2，1 )； //a-c graph.insert edge (1，2，1 )； //B- c graph.insert edge (1，3，1 )； //B- d graph.insert edge (1，4，1 )； //B-E //显示邻接结矩阵graph.showGraph (； //dfs测试system.out.println(DFS: )； graph.dfs (； //A-B-C-D-E } //生成器公共图形(intn )//初始化矩阵edges=newint(n )； //vertexlistvertexlist=初始化新阵列(n )； //边数numOfEdges=0； } /** *功能说明：如果某个顶点第一个相邻节点的下标w * * @param index顶点索引* @return存在，则返回相应的下标，否则返回-1*/publicintgetfirstneighbor j () if ) Edges[index][j]
gt; 0) { return j; } } return -1; } /** * 功能描述：根据前一个邻接结点的下标来获取下一个邻接结点 * * @param v1 第1个顶点 * @param v2 第2个顶点，也就是邻节点 * @return int 邻节点的下一个邻节点 * @author cakin * @date 2021/3/29 */ public int getNextNeighbor(int v1, int v2) { for (int j = v2 + 1; j < vertexList.size(); j++) { if (edges[v1][j] > 0) { return j; } } return -1; } /** * 功能描述：深度优先遍历算法 * * @author cakin * @date 2021/3/29 * @param isVisited 节点是否被访问数组 * @param i 被访问节点的下标 * @return * @description: */ private void dfs(boolean[] isVisited, int i) { // 输出被访问节点 System.out.print(getValueByIndex(i) + "->"); // 将该结点设置为已经访问 isVisited[i] = true; // 查找结点i的第一个邻接结点w int w = getFirstNeighbor(i); while (w != -1) { // 找到该邻节点 if (!isVisited[w]) { // 递归进行深度优先遍历算法 dfs(isVisited, w); } // 如果w结点已经被访问过，找下一个邻节点 w = getNextNeighbor(i, w); } } /** * 功能描述：对 dfs 进行一个重载, 遍历所有的结点，并进行 dfs * * @author cakin * @date 2021/3/29 */ public void dfs() { isVisited = new boolean[vertexList.size()]; // 遍历所有的结点，进行 dfs for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisited[i]) { dfs(isVisited, i); } } } /** * 功能描述：返回结点的个数 * * @author cakin * @date 2021/3/28 */ public int getNumOfVertex() { return vertexList.size(); } /** * 功能描述：显示图对应的矩阵 * * @author cakin * @date 2021/3/28 */ public void showGraph() { for (int[] link : edges) { System.err.println(Arrays.toString(link)); } } /** * 功能描述：得到边的数目 * * @return 得到边的数目 * @author cakin * @date 2021/3/28 */ public int getNumOfEdges() { return numOfEdges; } /** * 功能描述：返回结点i(下标)对应的数据 * * @param i 节点下标 * @return 节点对应的数据 * @author cakin * @date 2021/3/28 * @description: 举例如下： * 0->"A" 1->"B" 2->"C" */ public String getValueByIndex(int i) { return vertexList.get(i); } /** * 功能描述：返回v1和v2的权值 * * @param v1 第1个顶点的下标 * @param v2 第2个顶点的下标 * @return int 两个顶点间的权值 * @author cakin * @date 2021/3/28 */ public int getWeight(int v1, int v2) { return edges[v1][v2]; } /** * 功能描述：插入结点 * * @param vertex 节点的数据 * @author cakin * @date 2021/3/28 */ public void insertVertex(String vertex) { vertexList.add(vertex); } /** * 功能描述：添加边 * * @param v1 第1个顶点对应的下标 * @param v2 第2个顶点对应的下标 * @param weight 表示第1个顶点和第2个顶点的权重 */ public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }} 4 测试 [0, 1, 1, 0, 0][1, 0, 1, 1, 1][1, 1, 0, 0, 0][0, 1, 0, 0, 0][0, 1, 0, 0, 0]dfs:A->B->C->D->E->