图的遍历之BFS&DFS

缘起

图是一种典型的非线性数据结构. 但是人是很笨的. 人本质上只会研究线性的数据结构. 所以自然的想法就是通过遍历将非线性转换为线性. 树的遍历其实也是在做这样一件事情. 所以图的遍历算法就显得尤为重要了.

分析

图的遍历分为 深搜（dfs） 和宽搜（bfs）两种.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

#define LOCAL
using namespace std;

#define MAX_VERTEX_NUM 10


void printvertex(char c){ putchar(c);}

struct Graph
{
	// 使用邻接链表法构建图模型
	typedef struct Edge
	{
		char end;// 数据是字符
		Edge *next;
		Edge(char end):end(end),next(0){}
	}*EdgePi; // 定义指针

	typedef struct Vertex
	{
		char v;
		Edge *first;
	} ADJ[MAX_VERTEX_NUM]; // 定义数组

	int vertextnum, edgenum;
	bool isvisited[MAX_VERTEX_NUM]; // 是否遍历过
	ADJ adj;
	Graph(int vertextnum, int edgenum):vertextnum(vertextnum),edgenum(edgenum)
	{
		for (int i = 0; i<vertextnum;i++)
		{
			adj[i].v = i+'A';
			adj[i].first = 0;
		}
		cout << "输入每条边的起点终点, 起点在前, 终点在后, 不同边换行" << endl;
		char start, end;
		for (int i = 0; i<edgenum; i++)
		{
			getchar();
			scanf("%c %c", &start, &end);
			Edge *e = new Edge(end);
			e->next = adj[start-'A'].first;
			adj[start-'A'].first = e;
		}
	}

	int dfs() // 递归版本的深搜
	{
		memset(isvisited,0,sizeof(isvisited)); // 初始化
		int n = 0; // 连通分支的个数  这里仅仅在 递归版本的深搜中展示了如何使用搜索来求(无向图)连通分支的个数, 其实对于 栈版本的深搜和bfs是完全一样的原理的
		for (int i = 0; i<vertextnum; i++)
		{
			if (!isvisited[i])
			{
				isvisited[i] = true;
				n++;
				gao(i, printvertex);
			}
			
		}
		cout<<endl;
		return n;
	}

	void dfs_stack() // 栈版本的深搜, 注意, 既然是递归转栈, 为什么不用记录栈顶元素选择的状态呢? 本质上是因为这里 isvisited当递归返回的时候不需要改回来,则通过isvisited自动的就记录下来了之前已经选择过的状态. 而如果isvisited要改回来的话, 就不能通过 isvisited 知道已经选择过的状态了
	{
		memset(isvisited,0,sizeof(isvisited)); // 初始化
		xxx(0,printvertex);
		cout<<endl;
	}

	// 宽搜
	void bfs(void(*visit)(char))
	{
		memset(isvisited,0,sizeof(isvisited)); // 初始化
		queue<Vertex> q;
		q.push(adj[0]);
		isvisited[adj[0].v - 'A'] = true;
		while(!q.empty())
		{
			Vertex vtx = q.front();
			visit(vtx.v);
			q.pop();
			for (int i =0; i<vertextnum;i++)
			{
				if (!isvisited[i] && isconnected(vtx.v - 'A', i))
				{
					isvisited[i] = true;
					printf("\t%c-->%c\n", vtx.v, adj[i].v); // 遍历的过程中把边打印出来
					q.push(adj[i]);
				}
			}
		}
		cout<<endl;
	}

private:
	void gao(int cur, void (*visit)(char)) // cur 是当前节点在图的顶点数组中的索引，visit是怎么做
	{
		visit(adj[cur].v);
		for (int i = 0; i < vertextnum; i++)
		{
			if (!isvisited[i] && isconnected(cur, i)) // 为了提高效率, 将 isvisited的判断放在前面
			{
				printf("\t%c-->%c\n", adj[cur].v, adj[i].v); // 遍历的过程中把边打印出来
				isvisited[i] = true;
				gao(i, visit); // 注意, 这里不需要返回之后将isvisited改回来, 因为这是遍历而不是搜索
			}
		}
	}

	void xxx(int start, void(*visit)(char))
	{
		stack<Vertex> s;
		s.push(adj[start]);
		visit(adj[start].v);
		isvisited[start] = true;
		while(!s.empty())
		{
			int nxt = getnextconnected(s.top().v-'A'); // 找到下一个与之连通的索引
			if (~nxt) // 如果找到了
			{
				visit(adj[nxt].v);
				isvisited[nxt] = true;
				printf("\t%c-->%c\n", s.top().v, adj[nxt].v); // 遍历的过程中把边打印出来
				s.push(adj[nxt]);
			}
			else s.pop(); // 没找到的话, 则就是到底了, 就要弹栈了(因为前面已经无路可走了)
		}
	}

	bool isconnected(int i, int j) // adj[i]能否到adj[j]
	{
		EdgePi p = adj[i].first;
		while(p) 
		{
			if (p->end==adj[j].v) return true;
			p = p->next;
		}
		return false;
	}

	int getnextconnected(int i) // 找到下一个和adj[i]相邻的顶点并返回其索引
	{
		EdgePi p = adj[i].first;
		while (p)
		{
			if (!isvisited[p->end-'A'])return p->end-'A';
			p = p->next;
		}
		return -1; // 没找到
	}
};



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	cout << "输入顶点数和边的数目" << endl;
	int vertexnum, edgenum;
	scanf("%d %d", &vertexnum, &edgenum);
	Graph *g = new Graph(vertexnum, edgenum);
	cout << "存在" << g->dfs() <<"个连通分支"; // 递归版本的深搜
	//g->dfs_stack(); // 栈版本（即非递归）的深搜
	//g->bfs(printvertex);  // 宽搜
	return 0;
}

后记

其实各种搜索框架的本质不同就是如何对待发现的顶点. 深搜是最后处理最先发现的顶点（对应数据结构就是栈），而宽搜不同, 宽搜是最先处理最先发现的顶点（对应的数据结构就是队列）

从上面的算法可以看出，利用 dfs或者bfs 可以方便的求出无向图的连通分支的个数. 进而判断无向图是否连通. 后面（【1】）其实会知道, 并查集也是一个求出无向图连通分支个数，进而判定无向图是否连通的算法.

其实著名的泛洪算法（bloodfill）既可以使用dfs也可以使用bfs. 即沿着像素的四个方向拓展.

参考

【1】https://yfsyfs.github.io/2019/05/25/%E6%97%A0%E5%90%91%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91-MST-%E4%B9%8BKruskal%E7%AE%97%E6%B3%95/