图的BFS以及DFS递归非递归实现
image.png
本文所使用的所有邻接表以及邻接矩阵定义均在之前博客，这里不再赘述
一、深度优先遍历DFS（Depth-first search）
1.1.1 DFS递归邻接表实现原理
图的深度优先搜索遍历(DFS)类似于二叉树的先序遍历。它的基本思想是:首先访问出发点v,并将其标记为已访问过;然后选取与v邻接的未被访问的任意一个顶点w，并访问它:再选取与w邻接的未被访问的任一顶点并访问，以此重复进行。当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个并重复上述访问过程，直至图中所有顶点都被访问过为止。
/**
* @param graph 邻接表
* @param i 开始节点下标
*/
public static void dfsRecursion(AGraph graph, int i) {
ArcNode p;
visited[i] = 1;
dfsToString(graph, i);
p = graph.adjList[i].firstArc;
while (p != null) {
//如果没有访问过，则递归
if (visited[p.adjvex] == 0) {
dfsRecursion(graph, p.adjvex);
}
p = p.nextArc;
}
}
public static void dfsToString(AGraph graph, int i){
System.out.print(graph.adjList[i].name + " ");
}
1.1.2 DFS递归邻接矩阵实现原理
使用邻接矩阵实现DFS递归思路上和邻接表基本是一样的.不同的就是每次检索所有节点与当前节点是否有连接
/**
* @param graph
* @param i
*/
public static void dfsRecursionMatrix(MGraph graph, int i) {
visited[i] = 1;
System.out.print(graph.vex[i].no + " ");
for (int j = 0; j < graph.n; j++) {
//因为是无权无向图，所以权值默认为1
if(graph.edges[i][j] == 1 && visited[j] == 0){
dfsRecursionMatrix(graph,j);
}
}
}
1.2.1 DFS非递归邻接表实现
关于非递归的DFS实现，查阅了20多篇博客，发现网上大部分的邻接表实现非递归都是有问题的，终于在一篇博客中得到正解。
https://www.cnblogs.com/exciting/p/10102661.html
这里介绍下简单思路：
- 取第一个节点信息入栈
- 若栈不为空，取栈顶元素ArcNode p
- 遍历边节点p,如果存在visited[p.adjvex] == 0,即没用访问过，那么该元素入栈，将visited[p.adjvex] 置为1，同时p等于栈顶节点（也就是刚入栈元素）的firstArc
- 如果p已经访问过了，那么p = p.nextArc
- 如果遍历到p = null时，跳出内循环，将栈顶元素出栈（关键）
最后一步是关键，网上看到的版本大多是元素不出栈，内层循环入栈之后 break,或者是定义外循环次数为n次，我都试过，是不正确的。
拿本文例子按上述步骤解释：假设从1节点入栈，p=4节点，4节点没有被访问过，4节点入栈，之后无论跳出循环还是其他操作，p = 4节点的firstArc,即为1，1已经访问过，所以p = p.nextArc = null。结束循环，p取栈顶元素4的firstArc,依然是1。陷入死循环。可能解释不是很清楚，百度搜一下非递归代码看下应该就知道了。
内循环结束如果出栈的话，栈顶4出栈，栈顶变为1,1访问下一节点4， visited[4]=1，跳过访问下一节点，正解(节点4已经输出值了，如果需要保存出栈的顺序节点，那么需要额外定义一个集合来存储)
下面给出代码：
/**
* @param graph 邻接表
* @param i 起点下标
*/
public static void dfsNoRecursion(AGraph graph, int i) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int[] visited = new int[graph.verNum];
visited[i] = 1;
stack.push(i);
System.out.print(graph.adjList[i].name + " ");
ArcNode p;
while (!stack.isEmpty()) {
p = graph.adjList[stack.getFirst()].firstArc;
while (p != null) {
if (visited[p.adjvex] == 0) {
visited[p.adjvex] = 1;
System.out.print(graph.adjList[p.adjvex].name + " ");
stack.push(p.adjvex);
p = graph.adjList[p.adjvex].firstArc;
} else {
p = p.nextArc;
}
}
//p=null表明栈顶元素相邻节点都已经遍历过了
if (p == null) {
stack.pop();
}
}
}
1.2.2 DFS非递归邻接矩阵实现
非递归使用邻接矩阵和非递归使用邻接表区别仅仅在于遍历的方式。
邻接表是取栈顶的firstArc，然后next向下遍历直到找到没有遍历过的节点，然后让p等于新的栈顶的firstArc。
邻接矩阵是取栈顶节点，然后在邻接矩阵中遍历栈顶节点相邻的元素，如果存在，visited[j] = 1,入栈，跳出循环.更新k为最新的栈顶节点
/**
* @param graph 邻接矩阵
* @param i 起点下标
*/
public static void dfsNoRecursionMatrix(MGraph graph, int i) {
int[] visited = new int[graph.n];
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(i);
System.out.print(stack.getFirst() + " ");
visited[i] = 1;
while (!stack.isEmpty()) {
int k = stack.getFirst();
int j = 0;
for(j = 0; j < graph.n; j++) {
if(graph.edges[k][j] == 1 && visited[j] == 0) {
stack.push(j);
visited[j] = 1;
System.out.print(stack.getFirst() + " ");
break;
}
}
//如果j = n,与j相邻的节点都访问结束了
if (j == graph.n) {
stack.pop();
}
}
}
二、广度优先遍历(Breadth-First-Search)
广度优先遍历这里通过邻接表非递归的方式实现，如果我们熟悉二叉树的层次遍历，那么广度优先遍历思路基本一致。
我们利用队列，首节点入队，相邻节点依次入队，当全部相邻节点入队之后，出队遍历下一层。
文章可能输出方式不是特别规范，因为下标和节点信息都是一致的，即下标i, graph.adjList[k].name , 以及ArcNode的adjvex属性表示的都是一样的。
/**
*
* @param graph 邻接表
* @param i 起始下标
*/
public static void bfsNoRecursion(AGraph graph, int i) {
int[] visited = new int[graph.verNum];
ArrayDeque<Integer> queue = new ArrayDeque<>();
//顶点入队
queue.add(i);
visited[i] = 1;
while (!queue.isEmpty()) {
//顶点出队
int k = queue.poll();
System.out.print(graph.adjList[k].name + " ");
ArcNode p = graph.adjList[k].firstArc;
while (p != null) {
//没有被访问过的节点入队
if (visited[p.adjvex] == 0) {
queue.add(p.adjvex);
visited[p.adjvex] = 1;
}
p = p.nextArc;
}
}
}
三、非连通图的DFS,BFS
上述的操作都是针对于连通图来讲的。对于非连通图，只需要将遍历函数放到一个循环中，循环检测图中的每一个顶点，如果当前节点没有被访问，则调用上述函数从这个顶点遍历
public void noConnectDfs(AGraph graph){
for(int i = 0; i < graph.verNum) {
if (visited[i] == 0) {
dfsNoRecursion(graph,i);
}
}
}
public void noConnectBFS(AGraph graph){
for(int i = 0; i < graph.verNum) {
if (visited[i] == 0) {
bfsNoRecursion(graph,i);
}
}
}
四、测试代码
以上就是递归非递归的实现方法，可能类的成员变量名称和教材略有不同，但表示意思都是一样的。关于邻接表和邻接矩阵的创建，请阅读上一篇文章。
下面给出测试代码：
public static void main(String[] args) {
//初始化邻接矩阵,6个节点
int n = 6;
EdgeElement[] elements = new EdgeElement[6];
elements[0] = new EdgeElement(0, 1);
elements[1] = new EdgeElement(0, 2);
elements[2] = new EdgeElement(0, 3);
elements[3] = new EdgeElement(1, 2);
elements[4] = new EdgeElement(1, 4);
elements[5] = new EdgeElement(4, 5);
String[] names = {"0", "1", "2", "3", "4", "5"};
MGraph mGraph = new MGraph(elements, names, n, GTypeConstant.NoDirectionNoWeight);
mGraph.graphToString();
//邻接表形式
AGraph aGraph = new AGraph(6, 6, names, elements, GTypeConstant.NoDirectionNoWeight);
aGraph.graphToString();
//初始化visited数组
DfsBfs.visited = new int[10];
System.out.println("执行DFS递归(邻接表)，初始节点为1");
dfsRecursion(aGraph, 1);
visited = new int[10];
System.out.println();
System.out.println("执行DFS递归(邻接矩阵)，初始节点为1");
dfsRecursionMatrix(mGraph, 1);
System.out.println();
System.out.println("执行DFS非递归(邻接表)，初始节点为1");
dfsNoRecursion(aGraph, 1);
System.out.println();
System.out.println("执行DFS非递归(邻接矩阵)，初始节点为1");
dfsNoRecursionMatrix(mGraph, 1);
System.out.println();
System.out.println("执行BFS非递归(邻接矩阵)，初始节点为1");
bfsNoRecursion(aGraph,1);
}
输出结果为：
0 1 1 1 0 0
1 0 1 0 1 0
1 1 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 1 0
输出邻接表存储情况：
0->3->2->1
1->4->2->0
2->1->0
3->0
4->5->1
5->4
执行DFS递归(邻接表)，初始节点为1
1 4 5 2 0 3
执行DFS递归(邻接矩阵)，初始节点为1
1 0 2 3 4 5
执行DFS非递归(邻接表)，初始节点为1
1 4 5 2 0 3
执行DFS非递归(邻接矩阵)，初始节点为1
1 0 2 3 4 5
执行BFS非递归(邻接矩阵)，初始节点为1
1 4 2 0 5 3
