县 住房和城乡建设局网站,分页网站,广州宣布5条优化措施,什么建站公司好4 图的遍历 图的遍历分为深度优先遍历和广度优先遍历两种。
4.1 深度优先遍历 深度优先遍历#xff08;Depth First Search#xff09;#xff0c;也称为深度优先搜索#xff0c;简称DFS#xff0c;深度优先遍历#xff0c;是指从某一个顶点开始#xff0c;按照一定的规…4 图的遍历 图的遍历分为深度优先遍历和广度优先遍历两种。
4.1 深度优先遍历 深度优先遍历Depth First Search也称为深度优先搜索简称DFS深度优先遍历是指从某一个顶点开始按照一定的规则访问并记录下一个未访问顶点。对于非连通图则是按连通分量采用同一规则进行深度优先遍历的方式以以下图为例 我们使用visited[vertexSize]来记录已访问的顶点先从A开始并把A加入到visited中访问规则是“下一个访问的顶点是最右手边的那个顶点”注意图上的小人是面向我们从上往下走的此时visited {A} 接下来依附于顶点A的边有(A,B)、(A,F)小人右手边的边是(A,B)因此延着(A,B)走visited {A, B}: 依附于顶点B的边有(B,C)、(B,I)、(B,G)小人右手边且没被走过的边是(B,C)于是延着边(B,C)走visited {A, B, C} 按照这个规则走走到F时visited {A, B, C, D, E, F} 这时小人的右手边有几条路从右至左依次是(F,A)、(F,G)、(F、E)但顶点A在visited中表示顶点A已经被访问过了所以排除(F,A)延着(F,G)走visited {A, B, C, D, E, F, G} 这时相对于顶点G小人可走的路从右到左依次是(G,B)、(G,D)、(G,HB和D已经在visited中因此跳过延着(G,H)走visited {A, B, C, D, E, F, G, H} 这是相对于顶点H小人可走的路从右到左依次是(H,D)、(H、E)但D和E都在visited中了这时让小人延原路返回即延着(H,G)走 但相对于顶点G可走的路(G,B)、(G,D)和(G,H)三条路对应的顶点B、D、H也都在visited中了无路可走了继续原路返回到顶点F仍然无路可走继续返回E仍无路可走继续返回D 这时发现了(D,I)这条路还没走过于是延着(D,I)走visited {A, B, C, D, E, F, G, H, I} 又无路可走了于是原路返回直到返回顶点A也就是开始的那个顶点表示图已遍历完。 再来总结一下深度遍历优先的过程 (1) 先定一个规则比如“延着依附于当前顶点中最左侧的未被访问的边进行迭代” (2) 从某一个顶点开始按定义的规则迭代 (3) 若有符合规则的边则继续往下迭代若无符合规则的边则一步一步原路返回查找可迭代的边 (4) 当原路返回到最开始的那个顶点时迭代完毕 实际上整体上是一个递归调度的过程主要就是找到“下一条边”。 注意深度优先遍历的规则并不是固定不变的只要最终结果遵循“按一定规则逐步访问结点的下一个邻边”即可。
4.1.1 邻接矩阵的深度优先遍历 我们举几个例子 对这些图使用深度优先遍历时找“下一条未被访问边”的方式是 (1) 从第一个顶点开始访问arc[0][1]、arc[0][2]…arc[0][n]找到第一个未被访问的边边的判断是如果为图则值为1表示存在边如果为网则值不为无穷大且arc[i][j]中i不等于j表示存在边 (2) 找到这个边后访问它假设这个边为arc[0][x] (3) 然后继续访问arc[x]找到x的未被访问的边即递归第(1)、(2)步直到所有关联的边都访问完 (4) 若此时结点还未迭代完则从第二个“未被访问的顶点”开始继续迭代 因此如上无向图的遍历过程如下所示 过程为 (0) iterate C (1) 遍历arc[0][j]寻找C相关的顶点找到(C,D)visit Cvisit D (2) 遍历arc[1][j]寻找D相关的顶点找到(D,C)两个顶点都被访问过跳过 (3) 找到(D,A)visit A (4) 遍历arc[2][j]寻找A相关的顶点找到(A,C)两个顶点都被访问过跳过 (5) 找到(A,D)两个顶点都被访问过跳过 (6) 找到(A,B)visit B (7) 遍历arc[3][j]寻找B相关的顶点找到(B,C)两个顶点都被访问过跳过 (8) 找到(B,D)值为0不相关跳过 (9) 找到(B,A)两个顶点都被访问过跳过 (10) 找到(B,F)visit F (11) 遍历arc[4][j]寻找F相关的顶点找到(F,C)值为0不相关跳过 (12) 找到(F,D)值为0不相关跳过 (13) 找到(F,A)值为0不相关跳过 (14) 找到(F,B)两个顶点都被访问过跳过 (15) 找到(F,E)visit E此时所有顶点均访问完毕结束 如上有向网的遍历过程如下所示 过程为 (0) iterate E (1) 迭代arc[0][j]寻找E指向的顶点找到E,Fvisit E然后发现数组值为无穷大不相关跳过 (2) 找到E,C值为无穷大不相关跳过 (3) 找到E,Avisit A (4) 迭代arc[3][j]寻找A指向的顶点找到A,E值为无穷大不相关跳过 (5) 找到A,F值为无穷大不相关跳过 (6) 找到A,C值为无穷大不相关跳过 (7) 找到A,B值为无穷大不相关跳过 (8) 找到A,Dvisit D (9) 迭代arc[5][j]寻找D指向的顶点找到D,E值为无穷大不相关跳过 (10) 找到D,Fvisit F (11) 迭代arc[1][j]寻找F指向的顶点找到F,E值为无穷大不相关跳过 (12) 找到F,C值为无穷大不相关跳过 (13) 找到F,A值为无穷大不相关跳过 (14) 找到F,B值为无穷大不相关跳过 (15) 找到F,D值为无穷大不相关跳过 (16) F处理完毕没有相关的顶点于是回退一步到D继续迭代arc[5][j]找到D,Cvisit C (17) 迭代arc[2][j]寻找C指向的顶点找到C,EE已被访问跳过 (18) 找到C,F值为无穷大不相关跳过 (19) 找到C,A值为无穷大不相关跳过 (20) 找到C,Bvisit B此时所有顶点均访问完毕结束 代码实现如下所示
/*** 对图进行深度优先遍历** author Korbin* date 2023-02-02 17:02:23**/
public ListT deepFirstTraverse() {ListT visitedVertex new ArrayList();boolean[] visited new boolean[vertexNum];for (int i 0; i vertexNum visitedVertex.size() vertexNum; i) {deepFirstTraverse(visitedVertex, visited, i);}return visitedVertex;}/*** 对图进行深度迭代** param visitedVertex 迭代结果* param visited 已访问过的顶点* param index 接着要迭代的结点* author Korbin* date 2023-02-02 17:26:43**/
public void deepFirstTraverse(ListT visitedVertex, boolean[] visited, int index) {// 取出当前顶点if (!visited[index]) {// 当前顶点未被访问才继续T ver vertex[index];visitedVertex.add(ver);visited[index] true;// 取出当前顶点可走的边for (int j 0; j arc[index].length visitedVertex.size() vertexNum; j) {if (j ! index) {switch (type) {case UNDIRECTED:case DIRECTED: {// 无向图或有向图为1且顶点未被访问表示可以走try {int weight (int) (arc[index][j]);if (weight 1 !visited[j]) {// 可以继续往下走deepFirstTraverse(visitedVertex, visited, j);}} catch (NumberFormatException e) {// do nothing}break;}case UNDIRECTED_NETWORK:case DIRECTED_NETWORK: {// 无向图或有向网// 不为infinity且顶点未被访问if (!arc[index][j].equals(infinity) !visited[j]) {// 可以继续往下走deepFirstTraverse(visitedVertex, visited, j);}break;}}}}}
}4.1.2 邻接表的深度优先遍历 考虑如下有向图 从第一个顶点开始打到它未被访问的下一个顶点寻找的过程是先找firstEdge如果firstEdge指向的顶点已被访问则找firstEdge的next直到找到这个顶点为止接着访问这个顶点的指向下一个未访问的顶点寻找方式与第一个顶点相同。 该邻接表的遍历过程如下所示 整体过程为 (0) iterate C, visit C (1) 找顶点C相关的顶点找到(C,D)visit D (2) 找顶点D相关的顶点找到(D,C)两个顶点都被访问过跳过 (3) 继续找顶点D相关的顶点找到(D,A)visit A (4) 找顶点A相关的顶点找到(A,C)两个顶点都被访问过跳过 (5) 继续找顶点A相关的顶点找到(A,D)两个顶点都被访问过跳过 (6) 继续找顶点A相关的顶点找到(A,B)visit B (7) 找顶点B相关的顶点找到(B,C)两个顶点都被访问过跳过 (8) 继续找顶点B相关的顶点找到(B,A)两个顶点都被访问过跳过 (9) 继续找顶点B相关的顶点找到(B,F)visit F (10) 找顶点F相关的顶点找到(F,B)两个顶点都被访问过跳过 (11) 继续找顶点F相关的顶点找到(F,E)visit E此时所有顶点都访问完毕结束 相应地有向图的邻接表遍历过程如下所示 即 (0) iterate Cvisit C (1) 找顶点C指向的顶点找到C,Bvisit B (2) 找顶点B指向的顶点找到B,Avisit A (3) 找顶点A指向的顶点找到A,Dvisit D (4) 找顶点D指向的顶点找到D,C两个顶点都被访问过跳过 (5) 继续找顶点D指向的顶点找到D,B两个顶点都被访问过跳过 (6) 继续找顶点D指向的顶点找到D,Fvisit FF没有指向的顶点回退到D继续找顶点D指向的顶点D所有指向的顶点都已访问回退到B继续找顶点B指向的顶点B所有指向的顶点都已被访问回退到C (7) 继续找顶点C指向的顶点找到C,Evisit E此时所有顶点访问完毕结束 除了邻接表外还有一种逆邻接表逆邻接表使用的遍历方法与邻接表不同因为边集数组中保存的是每个顶点被指向的信息如下 逆邻接表的查找下一个未访问顶点的过程是“遍历边集数组找到firstEdge或nextEdge的为当前顶点的边集数组结点这个边集数组元素关联的第一个未被访问的顶点数组元素就是要找的下一个顶点”如上逆邻接表的遍历过程如下 (1) 从第一个顶点C开始迭代将它加入访问列表visit C (2) 迭代所有边集数组找到C指向的顶点因为C已被访问因此忽略它先看D只有边A,D与顶点C不相关跳过 (3) 看顶点A第一条边B,A与顶点C不相关跳过 (4) 继续看顶点A第二条边E,A与顶点C不相关跳过 (5) A的边看完了看B的边第一条边C,B找到顶点B是C指向的顶点且由于是按下标从小到大迭代的因此它一定是C指向的且下标最小的顶点因此visit B (6) 接下来看顶点B指向的顶点首先是顶点C因为已访问过因此忽略然后是顶点D有边A,D与顶点B不相关跳过 (7) 然后看顶点A有边B,AA是顶点B指向的顶点因此visit A (8) 接下来看顶点A指点的顶点顶点C已被访问仍然跳过然后是顶点D打到边A,D符合要求因此visit D (9) 接下来看顶点D指向的顶点前面的几个顶点C、D、A、B都已被访问过跳过看顶点F有边D,F符合要求因此visit F (10) 接下来看顶点F指向的顶点前面的几个顶点C、D、A、B、F都已被访问跳过看顶点E有边C,E与顶点F不相关跳过 (11) 这时所有顶点都迭代完毕但仍未访问到所有顶点因此回到第(1)步继续迭代顶点C已迭代过于是看顶点D顶点D已被访问跳过 (12) 继续迭代顶点A已被访问跳过 (13) 继续迭代顶点B已被访问跳过 (14) 继续迭代顶点F已被访问跳过 (15) 继续迭代顶点E未被访问因此visit E此时所有顶点都访问完毕遍历结束 代码实现如下所示
/*** 对图进行深度优先遍历** author Korbin* date 2023-02-02 19:59:26**/
public ListT deepFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];// 对于邻接表从第一个顶点开始处理先处理firstEdgefor (int i 0; i vertexNum vertexList.size() vertexNum; i) {if (!visited[i]) {System.out.println(iterate vertexes[i].getVertex());VertexNodeT, W vertexNode vertexes[i];vertexList.add(vertexNode.getVertex());visited[i] true;if (reverseAdjacency) {deepFirstTraverse(vertexList, visited, i);} else {deepFirstTraverse(vertexList, visited, vertexNode);}}}return vertexList;
}/*** 对使用逆邻接表存储的图进行深度优先遍历** param vertexList 遍历结果* param visited 访问列表* param index 当前遍历的下标* author Korbin* date 2023-02-06 18:13:34**/
public void deepFirstTraverse(ListT vertexList, boolean[] visited, int index) {int minRefIndex -1;// 找到index指向的下标最小的未访问的顶点boolean got false;for (int i 0; i vertexNum vertexList.size() vertexNum !got; i) {if (!visited[i]) {VertexNodeT, W vertexNode vertexes[i];EdgeNodeW edgeNode vertexNode.getFirstEdge();while (null ! edgeNode vertexList.size() vertexNum) {int edgeIndex edgeNode.getIndex();System.out.format(check %s-%s\r\n, vertexes[edgeIndex].getVertex(), vertexes[i].getVertex());if (edgeIndex index) {minRefIndex i;got true;break;}edgeNode edgeNode.getNext();}}}if (minRefIndex ! -1) {if (!visited[minRefIndex]) {// 访问这个顶点visited[minRefIndex] true;vertexList.add(vertexes[minRefIndex].getVertex());System.out.println(in vertexes[minRefIndex].getVertex());// 再访问这个顶点指向的顶点deepFirstTraverse(vertexList, visited, minRefIndex);}}
}/*** 对使用邻接表存储的图进行深度优先遍历** param vertexList 遍历结果* param visited 已访问的顶点* param vertexNode 正在访问的顶点* author Korbin* date 2023-02-03 20:26:22**/
public void deepFirstTraverse(ListT vertexList, boolean[] visited, VertexNodeT, W vertexNode) {EdgeNodeW firstEdge vertexNode.getFirstEdge();while (null ! firstEdge vertexList.size() vertexNum) {System.out.format(check %s-%s\r\n, vertexNode.getVertex(), vertexes[firstEdge.getIndex()].getVertex());int index firstEdge.getIndex();if (!visited[index]) {// 把它加入到遍历结果中然后递归处理它对应的顶点VertexNodeT, W nextNode vertexes[index];vertexList.add(nextNode.getVertex());visited[index] true;deepFirstTraverse(vertexList, visited, nextNode);}// 取下一个edgefirstEdge firstEdge.getNext();}
}4.1.3 十字链表的深度优先遍历 十字链表是在邻接表上的进一步优化因此十字链表的深度优先遍历方式与邻接表类似邻接表是处理firstEdge十字链表处理的是firstOut和nextHead因为firstOut就等于邻接表非逆邻接表的firstEdge而nextHead相关于邻接表的EdgeNode中的next大致逻辑为 (1) 从第一个顶点开始处理按如下规则 1) 如果顶点X未被访问则访问它 2) 找到顶点X的指向的下一个未被访问的顶点我们知道首先是firstOut然后是firstOut之后弧结点的nextHead 3) 找到这个顶点后访问它然后递归1)、2)步 (2) 继续迭代顶点列表中的其他顶点若还有未访问的顶点则按(1)的规则处理直到所有顶点处理完毕 以下面的十字链表为例 下图展示了它的深度优先遍历过程 (0) 先忽略所有firstIn相关的线然后iterate Evisit E (1) 找到E指向的顶点找到E,Avisit A (2) 找到A指向的顶点找到A,Dvisit D (3) 找到D指向的顶点找到D,Fvisit FF没有指向的顶点因此回退到D (4) 找到D指向的顶点找到D,Cvisit C; (5) 找到C指向的顶点找到C,E两个顶点都已被访问跳过 (6) 继续找到C指向的顶点C,Bvisit B此时所有顶点都已被访问结束 代码如下所示
/*** 对图进行深度优先遍历** author Korbin* date 2023-02-02 19:59:26**/
public ListT deepFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];// 对于邻接表从第一个顶点开始处理先处理firstEdgefor (int i 0; i vertexNum vertexList.size() vertexNum; i) {if (!visited[i]) {AcrossLinkVertexNodeT, W vertexNode vertexes[i];vertexList.add(vertexNode.getVertex());visited[i] true;deepFirstTraverse(vertexList, visited, vertexNode);}}return vertexList;
}/*** 对图进行深度优先遍历** param vertexList 遍历结果* param visited 已访问于列表* param vertexNode 待处理的顶点* author Korbin* date 2023-02-03 19:33:32**/
private void deepFirstTraverse(ListT vertexList, boolean[] visited, AcrossLinkVertexNodeT, W vertexNode) {AcrossLinkEdgeNodeW firstEdge vertexNode.getFirstOut();int nextIndex -1;while (null ! firstEdge vertexList.size() vertexNum) {// 指向的顶点下标为headIndexint index firstEdge.getHeadIndex();if (!visited[index]) {vertexList.add(vertexes[index].getVertex());visited[index] true;nextIndex index;// 递归处理下一个顶点的邻边deepFirstTraverse(vertexList, visited, vertexes[nextIndex]);}firstEdge firstEdge.getNextHead();}
}4.1.4 邻接多重表的深度优先遍历 考虑如下邻接多重表 第一个顶点是C它有三条关联的边分别是(C,A)、(C,B)和(C,D)我们把规则定为下一个未访问的邻边是在顶点数组中下标最小且未访问的那条边这个定义与邻接多重表的存储结构相同邻接多重表的存储设计是“firstEdge指向第一条边iLink指向下一条边下一条边的jVex必须为当前顶点下一条边的jLink指向下下一条边并不要求jVex为当前顶点下下一条边的jLink指向下下一条边并不要求jVex为当前顶点,依此类推”因此邻接多重表深度优先遍历的过程是 (1) 从第一个顶点X开始找到这个顶点下一条未被访问的边(X,Y) 1) 若能找到Y则访问Y并查找Y的下一条未被访问的边 2) 若Y不存在则原路返回走上一个顶点的未被访问的边 (2) 递归执行第(1)步直到找不到下一条未被访问的边时继续对第二个顶点进行处理直到所有顶点处理完毕。 如下为该邻接多重表的深度优先遍历过程 过程为 (0) iterate Cvisit C (1) 找C关联的顶点找到(C,D)visit D (2) 找D关联的顶点找到(D,A)visit A (3) 找A关联的顶点找到(A,C)两个顶点都已访问跳过 (4) 继续找A关联的顶点找到(D,A)两个顶点都已访问跳过 (5) 继续找A关联的顶点找到(A,B)visit B (6) 找B关联的顶点找到(B,C)两个顶点都已访问跳过 (7) 继续找B关联的顶点找到(A,B)两个顶点都已访问跳过 (8) 继续找B关联的顶点找到(F,B)visit F (9) 找F关联的顶点找到(F,B)两个顶点都已访问跳过 (10) 继续找F关联的顶点找到(E,F)visit E所有顶点都已访问结束 实现代码如下所示
/*** 对图进行深度优先遍历** return 遍历结果* author Korbin* date 2023-02-03 17:09:46**/
public ListT deepFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];for (int i 0; i vertexNum vertexList.size() vertexNum; i) {// 从第1个顶点开始找if (!visited[i]) {AdjacencyMultiVertexNodeT, W vertexNode vertexes[i];vertexList.add(vertexNode.getVertex());visited[i] true;deepFirstTraverse(vertexList, visited, vertexNode);}}return vertexList;}/*** 对图进行深度优先遍历** param vertexList 遍历结果* param visited 顶点是否已被访问* param vertexNode 待迭代的顶点* author Korbin* date 2023-02-03 17:44:43**/
public void deepFirstTraverse(ListT vertexList, boolean[] visited, AdjacencyMultiVertexNodeT, W vertexNode) {AdjacencyMultiEdgeNodeW firstEdge vertexNode.getFirstEdge();if (null ! firstEdge) {// firstEdge的关联顶点下标是jVexint index firstEdge.getJVex();int myIndex firstEdge.getIVex();if (!visited[index]) {// 未访问AdjacencyMultiVertexNodeT, W nextVertexNode vertexes[index];vertexList.add(nextVertexNode.getVertex());visited[index] true;// 然后处理index对应的顶点找它的下一个未访问的邻边deepFirstTraverse(vertexList, visited, nextVertexNode);} else {// 已访问// 下一个相关边是firstEdge的iLinkAdjacencyMultiEdgeNodeW nextEdge firstEdge.getILink();if (null ! nextEdge) {// 这个相关边的关联顶点是iVexindex nextEdge.getIVex();if (!visited[index]) {// 未访问AdjacencyMultiVertexNodeT, W nextVertexNode vertexes[index];vertexList.add(nextVertexNode.getVertex());visited[index] true;// 然后处理index对应的顶点找它的下一个未访问的邻边deepFirstTraverse(vertexList, visited, nextVertexNode);} else {// 已访问// 下一条以及下下条等相关边都是jLinknextEdge nextEdge.getJLink();while (null ! nextEdge vertexList.size() vertexNum) {// 关联顶点可能是iVex也可能是jVexint iVex nextEdge.getIVex();int jVex nextEdge.getJVex();if (iVex myIndex) {// 关联顶点是JVexif (!visited[jVex]) {AdjacencyMultiVertexNodeT, W nextVertexNode vertexes[jVex];vertexList.add(nextVertexNode.getVertex());visited[jVex] true;// 然后处理index对应的顶点找它的下一个未访问的邻边deepFirstTraverse(vertexList, visited, nextVertexNode);} else {nextEdge nextEdge.getJLink();}} else if (jVex myIndex) {// 关联顶点是IVexif (!visited[iVex]) {AdjacencyMultiVertexNodeT, W nextVertexNode vertexes[iVex];vertexList.add(nextVertexNode.getVertex());visited[iVex] true;// 然后处理index对应的顶点找它的下一个未访问的邻边deepFirstTraverse(vertexList, visited, nextVertexNode);} else {nextEdge nextEdge.getILink();}}}}}}}}4.1.5 边集数组的深度优先遍历 边集数组存储了每条边的begin、end信息由于无向图/网和有向图/网不同无向图/网的begin和end可以是边上的任何一个顶点因此对于无向图/网和有向图/网的遍历方式不同但整体方向差不多从下标最小的那个顶点开始找每个顶点关联的、未被访问的、下标最小的那个顶点进行访问。 先看无向图/网 从下标最小的那个顶点开始找即从顶点C开始找找它的边有(B,C)、(C,A)和(C,D)下标最小的关联顶点是D然后找D的边有(A,D)、(C,D)C被访问过了因此下一个顶点是C依此类推整体过程如下 整体过程是 (0) iterate C (1) 找到C关联的顶点找到(C,D)visit Cvisit D (2) 找到D关联的顶点找到(A,D)visit A (3) 找到A关联的顶点找到(A,B)visit B (4) 找到B关联的顶点找到(B,F)visit F (5) 找到F关联的顶点找到(F,E)visit E所有顶点访问完毕结束 无向图/网在找“下一个顶点”时找到的边中可以begin等于当前顶点也可以end等于当前顶点但有向网则不同只能找end为当前顶点的边看如下有向图 处理过程如下 整体过程是 (0) iterate E (1) 找E指向的顶点找到E,Avisit Evisit A (2) 找A指向的顶点找到A,Dvisit D (3) 找D指向的顶点找到D,Fvisit FF没有指向任何顶点回退到D (4) 找D指向的顶点找到D,Cvisit C (5) 找C指向的顶点找到C,Bvisit B此时所有顶点访问完毕结束 代码实现如下所示
/*** 对图进行深度优先遍历** return 遍历结果* author Korbin* date 2023-02-06 14:25:42**/
public ListT deepFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];for (int i 0; i vertexNum vertexList.size() vertexNum; i) {deepFirstTraverse(vertexList, visited, i);}return vertexList;
}/*** 对图进行深度优先遍历** param vertexList 遍历结果* param visited 访问记录* param index 待处理的下标* author Korbin* date 2023-02-06 14:25:58**/
public void deepFirstTraverse(ListT vertexList, boolean[] visited, int index) {// 找下标为i的顶点关联的边中关联顶点下标最小且未访问的顶点int minReleVertex -1;for (int j 0; j arc.length vertexList.size() vertexNum; j) {EdgeListEdgeNodeW edgeNode arc[j];int begin edgeNode.getBegin();int end edgeNode.getEnd();switch (type) {case UNDIRECTED:case UNDIRECTED_NETWORK: {if (begin index !visited[end]) {if (minReleVertex -1 || minReleVertex end) {minReleVertex end;}} else if (end index !visited[begin]) {if (minReleVertex -1 || minReleVertex begin) {minReleVertex begin;}}break;}case DIRECTED:case DIRECTED_NETWORK: {if (begin index !visited[end]) {if (minReleVertex -1 || minReleVertex end) {minReleVertex end;}}break;}}}if (!visited[index]) {// 访问该顶点visited[index] true;vertexList.add(vertex[index]);}if (minReleVertex ! -1 !visited[minReleVertex]) {// 访问该顶点的下标最小的关联顶点visited[minReleVertex] true;vertexList.add(vertex[minReleVertex]);// 接下来访问关联顶点的“下标最小的关联顶点”deepFirstTraverse(vertexList, visited, minReleVertex);// 处理完毕后应继续处理本顶点即“下一个顶点没有关联的顶点因此回退一步”deepFirstTraverse(vertexList, visited, index);}}4.2 广度优先遍历 广度优先遍历Breadth First Search又称为广度优先搜索简称BFS广度优先遍历有点类似于树的层序遍历。
4.2.1 邻接矩阵的广度优先遍历 考虑如下无向图 广度优先遍历的方法是从下标最小的顶点C开始访问C然后找到它的下一层访问它的下一层然后找到下一层的下一层访问它们依此类推。 在无向图中我们这边实现 (0) 我们先建一个队列用于辅助 (1) 从顶点C开始把它的下标加入队列此时队列里面只有C (2) 从队列中取出队头的数据即C的下标0访问C然后迭代arc[0][j]weight为1的依次加入队列此时队列从尾到头依次是B、A、D已访问列表里有{C} (3) 从队列中取出队头的数据即D的下标1访问D然后迭代arc[1][j]weight为1且未被访问的依次加入队列此时队列从尾到头依次是A、B、A已访问列表里有{C, D} (4) 从队列中取出队头的数据即A的下标2访问A然后迭代arc[2][j]weight为1且未被访问的依次加入队列此时队列从尾到头依次是B、A、B已访问列表里有{C, D, A} (5) 从队列中取出队头的数据即B的下标3访问B然后迭代arc[3][j]weight为1且未被访问的依次加入队列此时队列从尾到头依次是F、B、A已访问列表里有{C, D, A, B} (6) 从队列中取出队头的数据即A的下标2发现A已被访问跳过此时队列从尾到头依次是F、B已访问列表里有{C, D, A, B} (7) 从队列中取出队头的数据即B的下标3发现B已被访问跳过此时队列从尾到头依次是F已访问列表里有{C, D, A, B} (8) 从队列中取出队头的数据即F的下标4访问F然后迭代arc[4][j]weight为1且未被访问的依次加入队列此时队列从尾到头依次是E已访问列表里有{C, D, A, B, F} (9) 从队列中取出队头的数据即E的下标5访问E这时发现所有顶点均已访问完毕结束遍历得到结果{C, D, A, B, F, E} 有向图/网的实现类似考虑如下有向网 遍历过程如下所示 (1) 仍然使用一个辅助队列用于存储顶点下标从下标为0的顶点开始迭代先将它入队此时队列里面只有E (2) 从队列中取出队头数据即E的下标0访问它迭代arc[0][j]取出相关边有E,A将A插入队列此时队列里面只有A已访问顶点列表为{E} (3) 从队列中取出队头数据即A的下标3访问它迭代arc[3][j]取出相关边有A,D将D插入队列此时队列里面只有D已访问顶点列表为{E, A} (4) 从队列中取出队头数据即D的下标5访问它迭代arc[5][j]取出相关边有D,F、D,C、D,B将F、C、B依次插入队列此时队列从队尾到队头依次是B、C、F已访问顶点列表为{E, A, D} (5) 从队列中取出队头数据即F的下标1访问它迭代arc[1][j]取出相关边没有不进行处理此时队列从队尾到队头依次是B、C已访问顶点列表为{E, A, D, F} (6) 从队列中取出队头数据即C的下标2访问它迭代arc[2][j]取出相关边有C,E、C,B因为顶点E已被访问因此忽略它把B加入到队列此时队列从队尾到队头依次是B、B已访问顶点列表为{E, A, D, F, C} (7) 从队列中取出队头数据即B的下标4访问它发现所有顶点已访问完毕遍历结束得到结果{E, A, D, F, C, B} 代码实现如下所示
/*** 对图进行广度优先遍历** return 遍历结果* author Korbin* date 2023-02-06 19:33:16**/
public ListT breadthFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];LinkQueueInteger queue new LinkQueue();queue.init();for (int i 0; i vertexNum vertexList.size() vertexNum; i) {if (!visited[i]) {// 入队列LinkListNodeInteger node new LinkListNode();node.setData(i);queue.insert(node);System.out.println(iterate vertex[i]);while (!queue.isEmpty() vertexList.size() vertexNum) {// 一个个取出来访问并把它们的下一层放入队列node queue.delete();int index node.getData();if (!visited[index]) {vertexList.add(vertex[index]);visited[index] true;System.out.println(in vertex[index]);for (int j 0; j vertexNum vertexList.size() vertexNum; j) {if (j ! index !visited[j]) {boolean canInsert false;switch (type) {case UNDIRECTED:case DIRECTED: {// 无向图和有向图weight为1表示顶点相关try {int weight (int) arc[index][j];if (weight 1) {canInsert true;}} catch (NumberFormatException e) {// do nothing}break;}case UNDIRECTED_NETWORK:case DIRECTED_NETWORK: {// 无向网和有向网weight不为infinity表示顶点相关if (!arc[index][j].equals(infinity)) {canInsert true;}}}if (canInsert) {// 把下一层入队node new LinkListNode();node.setData(j);queue.insert(node);System.out.println(in queue vertex[j]);}}}}}}}return vertexList;
}4.2.2 邻接表的广度优先遍历 与邻接矩阵相同邻接表的广度优先遍历也借助队列实现其中逆邻接表的实现会更为复杂
/*** 对图进行广度优先遍历** return 遍历结果* author Korbin* date 2023-02-07 08:38:46**/
public ListT breadthFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];LinkQueueInteger queue new LinkQueue();queue.init();for (int i 0; i vertexNum vertexList.size() vertexNum; i) {System.out.println(iterate vertexes[i].getVertex());if (!visited[i]) {LinkListNodeInteger node new LinkListNode();node.setData(i);queue.insert(node);System.out.println(insert vertexes[i].getVertex());while (!queue.isEmpty() vertexList.size() vertexNum) {// 出队列node queue.delete();System.out.println(get vertexes[node.getData()].getVertex());int index node.getData();VertexNodeT, W vertexNode vertexes[index];// 访问该顶点if (!visited[index]) {vertexList.add(vertexNode.getVertex());visited[index] true;System.out.println(visit vertexNode.getVertex());if (!reverseAdjacency) {// 邻接表// 把指向的顶点一一入队EdgeNodeW edge vertexNode.getFirstEdge();while (edge ! null vertexList.size() vertexNum) {index edge.getIndex();if (!visited[index]) {System.out.println(insert vertexes[index].getVertex());LinkListNodeInteger childNode new LinkListNode();childNode.setData(index);queue.insert(childNode);}edge edge.getNext();}} else {// 逆邻表// 把指向的顶点一一入队for (int j 0; j vertexNum vertexList.size() vertexNum; j) {if (j ! index !visited[j]) {VertexNodeT, W tmpVertex vertexes[j];EdgeNodeW tmpEdge tmpVertex.getFirstEdge();while (null ! tmpEdge vertexList.size() vertexNum) {if (tmpEdge.getIndex() index) {// 入队System.out.println(tmpEdge.getIndex() index j);System.out.println(insert vertexes[j].getVertex());LinkListNodeInteger childNode new LinkListNode();childNode.setData(j);queue.insert(childNode);break;}tmpEdge tmpEdge.getNext();}}}}}}}}return vertexList;
}4.2.3 十字链表的广度优先遍历 十字链表的实现与邻接表的实现相同
/*** 对图进行广度优先遍历** return 遍历结果* author Korbin* date 2023-02-07 09:56:29**/
public ListT breadthFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];LinkQueueInteger queue new LinkQueue();queue.init();for (int i 0; i vertexNum vertexList.size() vertexNum; i) {System.out.println(iterate vertexes[i].getVertex());if (!visited[i]) {LinkListNodeInteger node new LinkListNode();node.setData(i);queue.insert(node);System.out.println(insert vertexes[i].getVertex());while (!queue.isEmpty() vertexList.size() vertexNum) {// 出队列node queue.delete();System.out.println(get vertexes[node.getData()].getVertex());int index node.getData();AcrossLinkVertexNodeT, W vertexNode vertexes[index];// 访问该顶点if (!visited[index]) {vertexList.add(vertexNode.getVertex());visited[index] true;System.out.println(visit vertexNode.getVertex());// 邻接表// 把指向的顶点一一入队AcrossLinkEdgeNodeW edge vertexNode.getFirstOut();while (edge ! null vertexList.size() vertexNum) {index edge.getHeadIndex();if (!visited[index]) {System.out.println(insert vertexes[index].getVertex());LinkListNodeInteger childNode new LinkListNode();childNode.setData(index);queue.insert(childNode);}edge edge.getNextHead();}}}}}return vertexList;}4.2.4 邻接多重表的广度优先遍历 上文有提到如何在邻接多重表中寻找关联的顶点在进行广度遍历时同样借助队列实现
/*** 对图进行广度优先遍历** return 遍历结果* author Korbin* date 2023-02-07 10:03:26**/
public ListT breadthFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];LinkQueueInteger queue new LinkQueue();queue.init();for (int i 0; i vertexNum vertexList.size() vertexNum; i) {if (!visited[i]) {System.out.println(iterate vertexes[i].getVertex());// 入队LinkListNodeInteger node new LinkListNode();node.setData(i);queue.insert(node);System.out.println(insert vertexes[i].getVertex());while (!queue.isEmpty() vertexList.size() vertexNum) {// 从队列中取出int index queue.delete().getData();System.out.println(get vertexes[index].getVertex());if (!visited[index]) {// 访问它AdjacencyMultiVertexNodeT, W vertexNode vertexes[index];vertexList.add(vertexNode.getVertex());visited[index] true;System.out.println(visit vertexNode.getVertex());// 取index关联的顶点AdjacencyMultiEdgeNodeW firstEdge vertexNode.getFirstEdge();if (null ! firstEdge) {int childIndex firstEdge.getJVex();if (!visited[childIndex]) {// 相关顶点入队LinkListNodeInteger childNode new LinkListNode();childNode.setData(childIndex);queue.insert(childNode);System.out.println(insert vertexes[childIndex].getVertex());}AdjacencyMultiEdgeNodeW edgeNode firstEdge.getILink();while (null ! edgeNode vertexList.size() vertexNum) {// 可能是iVex等于当前顶点也可能是jVex等于当前顶点int iVex edgeNode.getIVex();int jVex edgeNode.getJVex();if (iVex index !visited[jVex]) {// 相关顶点是jVexLinkListNodeInteger childNode new LinkListNode();childNode.setData(jVex);queue.insert(childNode);System.out.println(insert vertexes[jVex].getVertex());} else if (jVex index !visited[iVex]) {// 相关顶点是iVexLinkListNodeInteger childNode new LinkListNode();childNode.setData(iVex);queue.insert(childNode);System.out.println(insert vertexes[iVex].getVertex());}edgeNode edgeNode.getJLink();}}}}}}return vertexList;
}4.2.5 边集数组的广度优先遍历 边集数组仍然需要多次迭代边集数组才能找到相关的顶点
/*** 对图进行广度优先遍历** return 遍历结果* author Korbin* date 2023-02-07 10:30:36**/
public ListT breadthFirstTraverse() {ListT vertexList new ArrayList();boolean[] visited new boolean[vertexNum];LinkQueueInteger queue new LinkQueue();queue.init();boolean[] visitedArc new boolean[edgeNum];for (int i 0; i vertexNum vertexList.size() vertexNum; i) {if (!visited[i]) {System.out.println(iterate vertex[i]);// 入队LinkListNodeInteger node new LinkListNode();node.setData(i);queue.insert(node);System.out.println(insert vertex[i]);while (!queue.isEmpty() vertexList.size() vertexNum) {// 取出int index queue.delete().getData();System.out.println(get vertex[index]);if (!visited[index]) {// 访问它vertexList.add(vertex[index]);visited[index] true;System.out.println(visit vertex[index]);// 找它相关的顶点或指向的顶点switch (type) {case UNDIRECTED:case UNDIRECTED_NETWORK: {// 无向图/网for (int j 0; j edgeNum vertexList.size() vertexNum; j) {if (!visitedArc[j]) {System.out.println(iterate arc j);EdgeListEdgeNodeW edge arc[j];int begin edge.getBegin();int end edge.getEnd();if (begin index) {if (!visited[end]) {// 入队LinkListNodeInteger childNode new LinkListNode();childNode.setData(end);queue.insert(childNode);System.out.println(insert vertex[end]);}} else if (end index) {if (!visited[begin]) {// 入队LinkListNodeInteger childNode new LinkListNode();childNode.setData(begin);queue.insert(childNode);System.out.println(insert vertex[begin]);}}if (visited[begin] visited[end]) {visitedArc[j] true;}}}break;}case DIRECTED:case DIRECTED_NETWORK: {for (int j 0; j edgeNum vertexList.size() vertexNum; j) {if (!visitedArc[j]) {System.out.println(iterate arc j);EdgeListEdgeNodeW edge arc[j];int begin edge.getBegin();int end edge.getEnd();if (begin index !visited[end]) {// 入队LinkListNodeInteger childNode new LinkListNode();childNode.setData(end);queue.insert(childNode);System.out.println(insert vertex[end]);}if (visited[begin] visited[end]) {visitedArc[j] true;}}}break;}}}}}}return vertexList;
}注意边集数组若不进行特殊处理的话每一层的顶点顺序取决于边集数组中结点顺序的定义。如下有向网 若定义为如下边集数组时 广度优先遍历过程为 广度优先遍历结果为EADBFC。 但如果把边集数组的定义做一些调整 广度优先遍历过程为 遍历结果为EADCBF与之前的遍历结果并不相同。 当然你也可以选择在取出所有相关的顶点后对这些顶点按下标排序那么广度优先遍历的结果就是固定的了与边集数组中结点的顺序无关。 注本文为程 杰老师《大话数据结构》的读书笔记其中一些示例和代码是笔者阅读后自行编制的。
