数据结构：图

数据结构：图

前言

在自动化程序分析中，图和树的一些算法起到了至关重要的作用，所以在开始自动化程序分析的研究前，我用了两天复习了一遍数据结构中的图。本章主要内容有图的基本概念，图的存储和图相关的经典算法，并在附录中附带上完整代码的仓库链接。

注：文章中并不会提到关于图的所有概念和定理，只有和程序分析中相关性比较大的那部分。文章中若有错误请指出，代码也存在可优化的空间，欢迎把你的优化代码提到issue中。

概念

顶点、边和度

数据结构中说的图是平面图，也就是由顶点和顶点间的连线组成的。图的符号表达式为$G=(V,E)$，其中G就是图，V是顶点集是有限非空集合，E是边集是二元子集。

和顶点相关的概念有度（记作D），而在有向图中度再度被分化为出度（记作I_D）和入度（记作O_D）。

注：对于度的助记符号是我自定义的，没有官方的定义。

无向图

图2.2.1无向图

该图中

$D(A)=2$，$D(B)=3$，$D(D)=3$，$D(C)=2$。

V = { A , B , C , D } \textcolor{orange}{V = \{A,B,C,D\}} V={A,B,C,D}

E = { < A , B > , < B , A > , < A , D > , < D , A > , < D , B > , < B , D > , < B , C > , < C , B > , < C , D > , < D , C > } \textcolor{orange}{E = \{<A,B>,<B,A>,<A,D>,<D,A>,<D,B>,<B,D>,<B,C>,<C,B>,<C,D>,<D,C>\}} E={<A,B>,<B,A>,<A,D>,<D,A>,<D,B>,<B,D>,<B,C>,<C,B>,<C,D>,<D,C>}

有向图

图2.3.1有向图

该图中

$I\_D(A)=1$，$O\_D(A)=1$，$I\_D(B)=2$，$O\_D(B)=1$，$I\_D(C)=0$，$O\_D(C)=2$，$I\_D(D)=2$，$O\_D(D)=1$。

V = { A , B , C , D } \textcolor{orange}{V = \{A,B,C,D\}} V={A,B,C,D}

E = { < A , B > , < D , A > , < B , D > , < C , B > , < C , D > } \textcolor{orange}{E = \{<A,B>,<D,A>,<B,D>,<C,B>,<C,D>\}} E={<A,B>,<D,A>,<B,D>,<C,B>,<C,D>}

权

权值是根据实际情况定义的。例如在程序分析中，我们可以把每个顶点看作是设置的探针，此时的权值可以表示为两个探针之间执行的时间，或者执行的指令数。通常在程序分析中用的是有向图，因为我们程序的指令执行都是有方向的，那么基于有向图，我们可以实现$数据流分析$。而无向图可应用于城市的规划上，例如每个顶点就是一座城市，权值可代表城市间的距离。然后可以基于图做一些规划，例如寻找最短路径。

图2.4.1带权有向图

图2.4.2带权无向图

完全图

图2.5.1完全图

完全图是无向图中衍生的一个概念。完全图的定义是图中任意节点与其他所有节点都相连。因此，通过观察图2.1.5，能够得到判定一个无向图是否为完全图的方法：
$$对于G=(V,E)而言，\forall v\in V,D(v)=N-1，（N表示图中所有顶点个数）。$$
即，任意一个图中的顶点的度等于图中所有顶点数减1。

环

环的定义是从起始点出发沿着邻接点走最终又回到了起始点，所经过的顶点就形成了一个环。

图2.6.1无向图

在图2.6.1中，有3个环：

1. $A->B->C->A$
2. $A->B->C->D->A$
3. $A->C->D->A$

图2.6.2有向图

在图2.6.2中，有两个环：

1. $A->B->C->A$
2. $A->B->C->D->A$

小节

从上面列出的图来看，可以归纳出以下图的基本定理：

1. 有向图中所有顶点的出度和等于所有顶点的入度和。
2. 图中所有顶点的度之和等于边的2倍。
3. 完全图中，任意一个顶点的度等于所有顶点数-1。

存储方式

邻接矩阵

在程序中，我们用一种叫做邻接矩阵的数据结构存储图，它是一个二维数组，数组的下标就是图中的各顶点，数组中的元素是个布尔值，表示两个顶点是否相邻。

程序中数组的下标是从0开始的，所以我们事先定义图中A是0，按字母顺序递增下标，则该图对应的邻接矩阵为：

注意：我这里规定了邻接矩阵的每一行r与每一列c的交点处，元素值为1代表图中顶点r与顶点c相邻，元素值为0表示不相邻。也就是说我是横着看的，当然，你也可以按照自己的习惯竖着看。但请一定要记住你的习惯，这在后面编码时要保持习惯的一致性，否则容易出问题。

算法

图遍历算法

图遍历算法的实际意义：用于获取从指定顶点出发能够到达哪些顶点，可判断图连通性和获取图的联通分量个数。

连通性的判断在实际应用中就太普遍了，例如网络拓扑中各个终端的联通检测，电力系统中的连通性检测，交通运输网中连通性检测等等。

图遍历算法有两种：

1. 广度优先搜索（BFS）：指定一个顶点v_1，将与v1相邻的顶点v_2,v_3,…,v_n一次性找出来，然后再分别以同样的方式找与v_2,v_3,…,v_n相邻的顶点，直到找不到相邻点或者遍历完图中所有顶点。
2. 深度优先搜索（DFS）：指定一个顶点v_1，找出一个与v_1相邻的顶点v_2，然后找与v_2相邻的顶点v_3，按这样的方式一直到找不到相邻顶点或者遍历完图中所有顶点。

BFS详细流程

1. 引入一个队列Q，用来记录与v_1相邻的顶点。引入一个结果路径resPath，保存v_1遍历的结果。转步骤2。
2. 引入一个布尔型数组visited，表示已探索过的顶点，防止重复探索。转步骤3。
3. 将v_1加入Q，并标记对应visited中的元素为true。转步骤4。
4. 从Q首部取出一个顶点v，循环遍历图中所有顶点v_i。在visited[v_i] == false，且 v_i与v相邻时，将v_i加入Q，并标记对应visited中的元素为true，转步骤5。
5. 重复步骤4，直到Q为空，即可得到指定v_1可到达的所有点。

std::shared_ptr<std::vector<uint32_t>> graph::bfs(uint32_t v)
{
	std::vector<uint32_t> resVector;
	std::queue<uint32_t> Q;
	bool* visited = nullptr;

	if (v == 0 || v > _NumOfVertex + 1) goto end_ret;

	visited = new(std::nothrow) bool[_NumOfVertex];
	if (visited == nullptr) goto end_ret;

	// 清除一下标记
	memset(visited, false, sizeof(bool) * _NumOfVertex);

	// 标记初始顶点为已访问
	visited[v-1] = true;
	// 初始顶点入队
	Q.push(v-1);
	// 遍历队列
	while (!Q.empty())
	{
		uint32_t p = Q.front();
		resVector.push_back(p+1);
		Q.pop();

		for (uint32_t i = 0; i < _NumOfVertex; i++)
		{
			// 依次找与p点相邻的点
			if (!visited[i] && _AdjMatrix[p * _NumOfVertex + i])
			{
				visited[i] = true;
				Q.push(i);
			}
		}
	}

end_ret:
	if (visited) delete[] visited;
	return std::make_shared<std::vector<uint32_t>>(resVector);
}
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

DFS详细流程

本小节讲解的是非递归的DFS实现。

1. 引入一个栈S，用来记录与v_1相邻的顶点。引入一个结果路径resPath，保存v_1遍历的结果。转步骤2。
2. 引入一个布尔型数组visited，表示已探索过的顶点，防止重复探索。转步骤3。
3. 引入一个布尔型变量recurse_over，表示正在递归。转步骤4。
4. 将v_1压栈，并标记对应visited中的元素为true。转步骤5。
5. 取栈顶元素v，标记recurse_over为false。循环遍历图中所有顶点，在visited[v_i] == false，且 v_i与v相邻时，将v_i压栈，并标记对应visited中的元素为true，标记recurse_over为true，跳出循环，转步骤6。
6. 在recurse_over为true的时候我们直接继续步骤5，此时就模拟了递归了。在recurse_over为false时表示递归结束，也就意味着以顶点v寻找邻接点过程结束，v就是最终的点，因此将v加入resPath，S弹出栈顶元素，继续步骤5，直到S为空。

std::shared_ptr<std::vector<uint32_t>> graph::dfs(uint32_t v)
{
	std::vector<uint32_t> resVector;
	std::stack<uint32_t> S;
	bool recurse_over;
	bool* visited = nullptr;

	if (v == 0 || v > _NumOfVertex + 1) goto end_ret;

	visited = new(std::nothrow) bool[_NumOfVertex];
	if (visited == nullptr || _AdjMatrix == nullptr) return nullptr;

	// 清除一下标记
	memset(visited, false, sizeof(bool) * _NumOfVertex);

	visited[v - 1] = true;
	S.push(v-1);

	while (!S.empty())
	{
		uint32_t p = S.top();
		recurse_over = true;

		for (uint32_t i = 0; i < _NumOfVertex; i++)
		{	
			if (!visited[i] && _AdjMatrix[p * _NumOfVertex + i])
			{
				visited[i] = true;
				S.push(i);
				recurse_over = false;
				// 只要找到一个邻接点就入栈，然后立马跳出循环，并对该点进行重复上面的操作
				// 实现模拟递归
				break;
			}
		}

		if (recurse_over)
		{
			resVector.push_back(p+1);
			S.pop();
		}
	}

end_ret:
	if (visited) delete[] visited;
	return std::make_shared<std::vector<uint32_t>>(resVector);
}
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

拓扑排序

拓扑排序是针对于无环图来讲的，同时它也可以用来检测图中是否存在环。

拓扑排序常用来表示存在依赖关系的事务。

场景

课程选修要求如图

图中的含义是有：

• 选修《软件开发》就需要先选修《C++语言》、《数据结构》、《数据结构》和《数据库设计》中的任意一门。

• 选修《C++语言》的前提是先选修《C语言》

• 选修《数据结构》的前提是先选修《C语言》

• 选修《数据库设计》的前提是先选修《数据结构》

如果对《软件开发》这门课程进行拓扑排序，则得到的结果为：

同时意味着这也是学习《软件开发》这门课程比较合理的学习路线。

详细流程

本节介绍的拓扑排序算法会扩展到无向图中，用来判断图是否存在环。

先来说指定一个顶点v，给出以这个顶点为终点的拓扑排序算法：

1. 引入一个队列Q，存放所有所有入度为0的顶点，而对无向图来说则存放度为1的顶点。
2. 引入一个变量resVector，用来存放拓扑排序的结果。
3. 如果是有向图则将所有入度为0的顶点放入Q，如果是无向图则将所有度为1的顶点放入Q。
4. 取Q首部元素p，把p加入resVector。如果p就是v则拓扑排序结束，否则将与p邻接的点v_i的入度减一。如果v_i的入度为0（有向图）或者度为1（无向图），则将v_i加入Q。
5. 循环步骤4，直到Q为空。此时resVector就是指定顶点v的拓扑排序结果。

std::shared_ptr<std::vector<uint32_t>> graph::topologySort(uint32_t v)
{
	std::vector<uint32_t> resVector;
	std::queue<uint32_t> Q;
	std::vector<uint32_t> V(_IsDirected ? _InDegree : _Degree);

	if (v == 0 && v > _NumOfVertex) goto end_ret;

	for (int32_t i = 0; i < _NumOfVertex; i++)
	{
		if ((_IsDirected && V[i] == 0) || (!_IsDirected && V[i] == 1)) Q.push(i);
	}

	while (!Q.empty())
	{
		int32_t p = Q.front();
		Q.pop();

		resVector.push_back(p + 1);

		if (p + 1 == v) break;

		for (int32_t i = 0; i < _NumOfVertex; i++)
		{
			if (_AdjMatrix[p * _NumOfVertex + i])
			{
				V[i] -= 1;
				if ((_IsDirected && V[i] == 0) || (!_IsDirected && V[i] == 1)) Q.push(i);
			}
		}
	}

end_ret:
	return std::make_shared<std::vector<uint32_t>>(resVector);
}	
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

再说说使用拓扑排序判断图中是否存在环的算法，与指定点的拓扑排序算法大同小异：

1. 引入一个队列Q，存放所有所有入度为0的顶点，而对无向图来说则存放度为1的顶点。
2. 引入整数型变量num，记录入度为0或者度为1的顶点数。
3. 如果是有向图则将所有入度为0的顶点放入Q，如果是无向图则将所有度为1的顶点放入Q，更新num。
4. 取Q首部元素p。如果p就是v则拓扑排序结束，否则将与p邻接的点v_i的入度减一。如果v_i的入度为0（有向图）或者度为1（无向图），则将v_i加入Q，更新num。
5. 循环步骤4，直到Q为空。此时num如果不等于图中所有顶点的数量，则说明图中存在环，否则就是无环。

bool graph::hasCycle()
{
	std::queue< uint32_t> Q;
	int32_t num = 0;


	std::vector<uint32_t> V(_IsDirected ? _InDegree : _Degree);

	for (int32_t v = 0; v < _NumOfVertex; v++)
	{
		if ((_IsDirected && V[v] == 0) || (_IsDirected && V[v] == 1))
		{
			Q.push(v);
			num += 1;
		}
	}

	while (!Q.empty())
	{
		int32_t v = Q.front();
		Q.pop();
		
		for (int32_t i = 0; i < _NumOfVertex; i++)
		{
			if (_AdjMatrix[v * _NumOfVertex + i])
			{
				V[i] -= 1;
				if ((_IsDirected && V[i] == 0) || (_IsDirected && V[i] == 1))
				{
					Q.push(i);
					num += 1;
				}
			}
		}
	}

	return num != _NumOfVertex;;
}
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

获取所有路径

场景

本小节主要讲的应用场景是给定一个起始点和终点，获取从起始点到达终点的所有路径。这种应用场景在程序分析可以是解析函数间的调用关系，请看下图：

假设图中各顶点代表函数A，B,…,H，图中反映的是他们之间的调用关系。我想知道从函数A到函数G都有哪些调用路径。从图中我们可以很清楚的知道有这些路径：

1. $A->B->F->G$

2. $A->D->F->G$

3. $A->C->E->G$

注意：一条路径上重复的点不走第二次。

那么如何让计算机去实现这种功能呢？

详细流程

整个算法基于DFS的思想，假设输入起始点为v1，终点为v2。

1. 引入栈S，用来表示当前探索的顶点。
2. 引入序列path，用来保存一条探索到的路径。
3. 引入序列resVec，保存所有路径。
4. 引入序列pos，记录已探索顶点的邻接点在邻接矩阵中的位置。
5. 引入逻辑变量recursed，表示处于模拟递归中。
6. 引入序列visited，记录已访问的顶点。
7. 将起始点v1压栈，设置对应的visited元素为true，将v1加入path。
8. 取S顶部元素v，设置recursed = false，从pos[v]开始遍历所有与v邻接的点vi。
9. 如果visited[vi] == false，且vi == v2 - 1，则说明找到了一条路径，将path加入resVec，否则转入步骤10。
10. 设置visited[vi] = true，将vi压入S，并加入path，pos[vi] = 0，pos[v] = i+1（i为循环计次），recursed = true。转到步骤11.
11. 如果recursed == false，从path中删除最近一次添加的元素，pos[v] -=1，visited[v] = false，S弹栈。这一步实现了回溯。转入步骤8
12. 循环步骤8到步骤11，直到栈为空，resVec保存了所有路径。

std::shared_ptr<std::vector<std::vector<uint32_t>>> graph::getAllPath(uint32_t v1, uint32_t v2)
{
	std::stack<uint32_t> S;
	std::vector<uint32_t> path;
	std::vector<std::vector<uint32_t>> resVec;
	std::vector<int32_t> pos;
	bool recursed = false;
	bool* visited = nullptr;

	if (v1 == 0 || v1 > _NumOfVertex || (v2 == 0 || v2 > _NumOfVertex)) goto end_exit;

	visited = new(std::nothrow) bool[_NumOfVertex];
	if (visited == nullptr) goto end_exit;
	// 初始化
	for (uint32_t i = 0; i < _NumOfVertex; i++)
	{
		visited[i] = false;
		pos.push_back(0);
	}

	S.push(v1 - 1);
	path.push_back(v1);
	visited[v1 - 1] = true;

	while (!S.empty())
	{
		auto v = S.top();
		recursed = false;

		for (uint32_t i = pos[v]; i < _NumOfVertex; i++)
		{
			if (!visited[i] && _AdjMatrix[v * _NumOfVertex + i])
			{
				if (i == v2 - 1)
				{
					std::vector<uint32_t>tmpVec(path);
					tmpVec.push_back(i + 1);
					resVec.push_back(tmpVec);
				}
				else
				{
					visited[i] = true;
					S.push(i);
					path.push_back(i + 1);
					pos[i] = 0;

					pos[v] = i + 1;
					recursed = true;
					break;
				}
			}
		}

		if (!recursed)
		{// 回溯大法
			path.pop_back();
			v = S.top();
			if(pos[v]) pos[v] -= 1;
			visited[v] = false;
			S.pop();
		}
	}
	
end_exit:
	if (visited) delete[] visited;
	return std::make_shared<std::vector<std::vector<uint32_t>>>(resVec);
}
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

寻最短/长路径

前面在权一小节中提到过寻最短路径的应用场景，同样在程序分析中有很重要意义。说到寻最短路径不得不提到一个著名算法——Dijkstra，应用的场景是寻单源点下的最短路径。也就是说指定一个起始点，该算法会取得该点到图中各点最短的路径距离。而我们稍微增加一些代码就能实现获取起始点的最短/长路径和距离值。

注意：本小节提到的寻最短/长路径是基于带权路径图来说的，无权图不适用这个算法。

整个算法基于BFS思想，假设输入起始点为v1，具体操作如下：

1. 引入队列Q，表示正在探索的顶点。
2. 引入序列dis，表示起始点v1到各点的最短/长距离。
3. 引入布尔型序列visited，表示已探索过的顶点。
4. 引入path，保存v1到各顶点的最短路径。
5. 将起始点加入Q，并标记对应visited中的元素。
6. 取Q首部元素v，Q弹出首部元素。遍历所有与v相邻的vi，在visited[vi] == falss时，动态计算距离w。计算方法：v1到v的距离（dis[v]）加上v到vi的距离（dis[vi]）。如果w小于之前的值prev_dis，则更新w，此时将vi视作本次所有路径中最短的终点s。如果w小于dis[vi]，则dis[vi] = w，更新最长路径。同样更新path，方法是拷贝之前的路径，并新增vi。
7. 如果s不等于v，则设置visited[s] = true，并加入Q。
8. 循环步骤6~7，直到Q为空。此时，path中保存了v1到图中各点的最短路径。

最长路径的求法，就是在比较路径的时候将“<”换成“>”，不再赘述。

std::shared_ptr<std::unordered_map<uint32_t, std::vector<uint32_t>>> graph::DijkstraAlogrithm(
	uint32_t v1,
	std::vector<uint32_t>& dis,
	bool reverse)
{
	std::unordered_map<uint32_t, std::vector<uint32_t>> path;
	std::queue<uint32_t> Q;
	uint32_t v;
	bool* visited = nullptr;

	visited = new(std::nothrow) bool[_NumOfVertex];
	if (visited == nullptr) goto end_ret;

	// 清除一下标记
	memset(visited, false, sizeof(bool) * _NumOfVertex);
	
	for (uint32_t i = 0; i < _NumOfVertex; i++)
	{
		// 初始化指定源点到各个顶点的最短路径
		path.insert(std::pair<uint32_t, std::vector<uint32_t>>(i, std::vector<uint32_t>()));
		// 初始化距离
		if (i == v1 - 1) dis.push_back(0);
		else dis.push_back(reverse ? 0 : -1);
	}

	Q.push(v1 - 1);
	visited[v1 - 1] = true;

	while (!Q.empty())
	{
		auto v = Q.front();
		Q.pop();
		uint32_t s = v;
		uint32_t prev_dis = reverse ? 0 : -1;

		for (uint32_t i = 0; i < _NumOfVertex; i++)
		{
			if (!visited[i] && _AdjMatrix[v * _NumOfVertex + i])
			{
				auto w = _Weight[v * _NumOfVertex + i] + dis[v];

				if (reverse)
				{
					if (prev_dis < w)
					{
						// 更新本次寻找到的最长路径长度
						prev_dis = w;
						s = i; // s 始终指向本次寻找到的最长路径的终点
					}

					if (w > dis[i])
					{
						// 动态更新最长路径
						dis[i] = w;
						if (path[v].size()) path[i] = std::vector<uint32_t>(path[v]);
						path[i].push_back(v + 1);
					}
				}
				else
				{
					if (prev_dis > w)
					{
						// 更新本次寻找到的最短路径长度
						prev_dis = w;
						s = i; // s 始终指向本次寻找到的最短路径的终点
					}

					if (w < dis[i])
					{
						// 动态更新最短路径
						dis[i] = w;
						if (path[v].size()) path[i] = std::vector<uint32_t>(path[v]);
						path[i].push_back(v + 1);
					}
				}
			}
		}

		if (s != v)
		{
			// 将本次最短路径终点标记为已访问，意味着从指定源点到s 的最短路径已经找到。
			visited[s] = true;
			Q.push(s);
		}
	}
	
end_ret:
	if (visited) delete[] visited;
	return std::make_shared<std::unordered_map<uint32_t, std::vector<uint32_t>>>(path);
}
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

附录

完整代码清移步我的代码仓库：https://github.com/singlefreshBird/Algorithm