大话数据结构-图的深度优先遍历和广度优先遍历
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,H），B和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 C，visit 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,F>，visit E，然后发现数组值为无穷大，不相关，跳过；
(2) 找到<E,C>，值为无穷大，不相关，跳过；
(3) 找到<E,A>，visit A；
(4) 迭代arc[3][j]，寻找A指向的顶点，找到<A,E>，值为无穷大，不相关，跳过；
(5) 找到<A,F>，值为无穷大，不相关，跳过；
(6) 找到<A,C>，值为无穷大，不相关，跳过；
(7) 找到<A,B>，值为无穷大，不相关，跳过；
(8) 找到<A,D>，visit D；
(9) 迭代arc[5][j]，寻找D指向的顶点，找到<D,E>，值为无穷大，不相关，跳过；
(10) 找到<D,F>，visit 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,C>，visit C；
(17) 迭代arc[2][j]，寻找C指向的顶点，找到<C,E>，E已被访问，跳过；
(18) 找到<C,F>，值为无穷大，不相关，跳过；
(19) 找到<C,A>，值为无穷大，不相关，跳过；
(20) 找到<C,B>，visit B，此时所有顶点均访问完毕，结束；
代码实现如下所示：
/**
* 对图进行深度优先遍历
*
* @author Korbin
* @date 2023-02-02 17:02:23
**/
public List<T> deepFirstTraverse() {
List<T> 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(List<T> 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 C，visit C；
(1) 找顶点C指向的顶点，找到<C,B>，visit B；
(2) 找顶点B指向的顶点，找到<B,A>，visit A；
(3) 找顶点A指向的顶点，找到<A,D>，visit D；
(4) 找顶点D指向的顶点，找到<D,C>，两个顶点都被访问过，跳过；
(5) 继续找顶点D指向的顶点，找到<D,B>，两个顶点都被访问过，跳过；
(6) 继续找顶点D指向的顶点，找到<D,F>，visit F；F没有指向的顶点，回退到D；继续找顶点D指向的顶点，D所有指向的顶点都已访问，回退到B；继续找顶点B指向的顶点，B所有指向的顶点都已被访问，回退到C；
(7) 继续找顶点C指向的顶点，找到<C,E>，visit 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,A>，A是顶点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 List<T> deepFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
// 对于邻接表，从第一个顶点开始处理，先处理firstEdge
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
System.out.println("iterate " + vertexes[i].getVertex());
VertexNode<T, 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(List<T> 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]) {
VertexNode<T, W> vertexNode = vertexes[i];
EdgeNode<W> 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(List<T> vertexList, boolean[] visited, VertexNode<T, W> vertexNode) {
EdgeNode<W> 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]) {
// 把它加入到遍历结果中，然后递归处理它对应的顶点
VertexNode<T, W> nextNode = vertexes[index];
vertexList.add(nextNode.getVertex());
visited[index] = true;
deepFirstTraverse(vertexList, visited, nextNode);
}
// 取下一个edge
firstEdge = 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 E，visit E；
(1) 找到E指向的顶点，找到<E,A>，visit A；
(2) 找到A指向的顶点，找到<A,D>，visit D；
(3) 找到D指向的顶点，找到<D,F>，visit F；F没有指向的顶点，因此回退到D；
(4) 找到D指向的顶点，找到<D,C>，visit C;
(5) 找到C指向的顶点，找到<C,E>，两个顶点都已被访问，跳过；
(6) 继续找到C指向的顶点<C,B>，visit B，此时所有顶点都已被访问，结束；
代码如下所示：
/**
* 对图进行深度优先遍历
*
* @author Korbin
* @date 2023-02-02 19:59:26
**/
public List<T> deepFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
// 对于邻接表，从第一个顶点开始处理，先处理firstEdge
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
AcrossLinkVertexNode<T, 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(List<T> vertexList, boolean[] visited, AcrossLinkVertexNode<T, W> vertexNode) {
AcrossLinkEdgeNode<W> firstEdge = vertexNode.getFirstOut();
int nextIndex = -1;
while (null != firstEdge && vertexList.size() < vertexNum) {
// 指向的顶点下标为headIndex
int 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 C，visit 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 List<T> deepFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
// 从第1个顶点开始找
if (!visited[i]) {
AdjacencyMultiVertexNode<T, 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(List<T> vertexList, boolean[] visited, AdjacencyMultiVertexNode<T, W> vertexNode) {
AdjacencyMultiEdgeNode<W> firstEdge = vertexNode.getFirstEdge();
if (null != firstEdge) {
// firstEdge的关联顶点下标是jVex
int index = firstEdge.getJVex();
int myIndex = firstEdge.getIVex();
if (!visited[index]) {
// 未访问
AdjacencyMultiVertexNode<T, W> nextVertexNode = vertexes[index];
vertexList.add(nextVertexNode.getVertex());
visited[index] = true;
// 然后处理index对应的顶点，找它的下一个未访问的邻边
deepFirstTraverse(vertexList, visited, nextVertexNode);
} else {
// 已访问
// 下一个相关边是firstEdge的iLink
AdjacencyMultiEdgeNode<W> nextEdge = firstEdge.getILink();
if (null != nextEdge) {
// 这个相关边的关联顶点是iVex
index = nextEdge.getIVex();
if (!visited[index]) {
// 未访问
AdjacencyMultiVertexNode<T, W> nextVertexNode = vertexes[index];
vertexList.add(nextVertexNode.getVertex());
visited[index] = true;
// 然后处理index对应的顶点，找它的下一个未访问的邻边
deepFirstTraverse(vertexList, visited, nextVertexNode);
} else {
// 已访问
// 下一条，以及下下条等，相关边都是jLink
nextEdge = nextEdge.getJLink();
while (null != nextEdge && vertexList.size() < vertexNum) {
// 关联顶点可能是iVex，也可能是jVex
int iVex = nextEdge.getIVex();
int jVex = nextEdge.getJVex();
if (iVex == myIndex) {
// 关联顶点是JVex
if (!visited[jVex]) {
AdjacencyMultiVertexNode<T, W> nextVertexNode = vertexes[jVex];
vertexList.add(nextVertexNode.getVertex());
visited[jVex] = true;
// 然后处理index对应的顶点，找它的下一个未访问的邻边
deepFirstTraverse(vertexList, visited, nextVertexNode);
} else {
nextEdge = nextEdge.getJLink();
}
} else if (jVex == myIndex) {
// 关联顶点是IVex
if (!visited[iVex]) {
AdjacencyMultiVertexNode<T, 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 C，visit 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,A>，visit E，visit A；
(2) 找A指向的顶点，找到<A,D>，visit D；
(3) 找D指向的顶点，找到<D,F>，visit F；F没有指向任何顶点，回退到D；
(4) 找D指向的顶点，找到<D,C>，visit C；
(5) 找C指向的顶点，找到<C,B>，visit B，此时，所有顶点访问完毕，结束；
代码实现如下所示：
/**
* 对图进行深度优先遍历
*
* @return 遍历结果
* @author Korbin
* @date 2023-02-06 14:25:42
**/
public List<T> deepFirstTraverse() {
List<T> 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(List<T> vertexList, boolean[] visited, int index) {
// 找下标为i的顶点关联的边中，关联顶点下标最小且未访问的顶点
int minReleVertex = -1;
for (int j = 0; j < arc.length && vertexList.size() < vertexNum; j++) {
EdgeListEdgeNode<W> 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 List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> queue = new LinkQueue<>();
queue.init();
for (int i = 0; i < vertexNum && vertexList.size() < vertexNum; i++) {
if (!visited[i]) {
// 入队列
LinkListNode<Integer> 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 List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> 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]) {
LinkListNode<Integer> 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();
VertexNode<T, W> vertexNode = vertexes[index];
// 访问该顶点
if (!visited[index]) {
vertexList.add(vertexNode.getVertex());
visited[index] = true;
System.out.println("visit " + vertexNode.getVertex());
if (!reverseAdjacency) {
// 邻接表
// 把指向的顶点一一入队
EdgeNode<W> edge = vertexNode.getFirstEdge();
while (edge != null && vertexList.size() < vertexNum) {
index = edge.getIndex();
if (!visited[index]) {
System.out.println("insert " + vertexes[index].getVertex());
LinkListNode<Integer> 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]) {
VertexNode<T, W> tmpVertex = vertexes[j];
EdgeNode<W> 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());
LinkListNode<Integer> 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 List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> 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]) {
LinkListNode<Integer> 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();
AcrossLinkVertexNode<T, W> vertexNode = vertexes[index];
// 访问该顶点
if (!visited[index]) {
vertexList.add(vertexNode.getVertex());
visited[index] = true;
System.out.println("visit " + vertexNode.getVertex());
// 邻接表
// 把指向的顶点一一入队
AcrossLinkEdgeNode<W> edge = vertexNode.getFirstOut();
while (edge != null && vertexList.size() < vertexNum) {
index = edge.getHeadIndex();
if (!visited[index]) {
System.out.println("insert " + vertexes[index].getVertex());
LinkListNode<Integer> 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 List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> 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());
// 入队
LinkListNode<Integer> 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]) {
// 访问它
AdjacencyMultiVertexNode<T, W> vertexNode = vertexes[index];
vertexList.add(vertexNode.getVertex());
visited[index] = true;
System.out.println("visit " + vertexNode.getVertex());
// 取index关联的顶点
AdjacencyMultiEdgeNode<W> firstEdge = vertexNode.getFirstEdge();
if (null != firstEdge) {
int childIndex = firstEdge.getJVex();
if (!visited[childIndex]) {
// 相关顶点入队
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(childIndex);
queue.insert(childNode);
System.out.println("insert " + vertexes[childIndex].getVertex());
}
AdjacencyMultiEdgeNode<W> edgeNode = firstEdge.getILink();
while (null != edgeNode && vertexList.size() < vertexNum) {
// 可能是iVex等于当前顶点，也可能是jVex等于当前顶点
int iVex = edgeNode.getIVex();
int jVex = edgeNode.getJVex();
if (iVex == index && !visited[jVex]) {
// 相关顶点是jVex
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(jVex);
queue.insert(childNode);
System.out.println("insert " + vertexes[jVex].getVertex());
} else if (jVex == index && !visited[iVex]) {
// 相关顶点是iVex
LinkListNode<Integer> 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 List<T> breadthFirstTraverse() {
List<T> vertexList = new ArrayList<>();
boolean[] visited = new boolean[vertexNum];
LinkQueue<Integer> 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]);
// 入队
LinkListNode<Integer> 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);
EdgeListEdgeNode<W> edge = arc[j];
int begin = edge.getBegin();
int end = edge.getEnd();
if (begin == index) {
if (!visited[end]) {
// 入队
LinkListNode<Integer> childNode = new LinkListNode<>();
childNode.setData(end);
queue.insert(childNode);
System.out.println("insert " + vertex[end]);
}
} else if (end == index) {
if (!visited[begin]) {
// 入队
LinkListNode<Integer> 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);
EdgeListEdgeNode<W> edge = arc[j];
int begin = edge.getBegin();
int end = edge.getEnd();
if (begin == index && !visited[end]) {
// 入队
LinkListNode<Integer> 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，与之前的遍历结果并不相同。
当然，你也可以选择在取出所有相关的顶点后，对这些顶点按下标排序，那么广度优先遍历的结果就是固定的了，与边集数组中结点的顺序无关。
注：本文为程 杰老师《大话数据结构》的读书笔记，其中一些示例和代码是笔者阅读后自行编制的。
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
14
0- 0
已为社区贡献3条内容
所有评论(0)