数据结构探险-05图篇

发表于   |   分类于   |  

数据结构探险之图篇-慕课网

1 图的基本概念

有向图和无向图

顶点、弧、出度／入度

边、邻接点

连通图

对于无向图中的每一个顶点，都能找到一个通往其它任意一个顶点的路径（直接或间接），则构成连通图。

完全图

在一个无向图中，任意两个顶点之间都存在连线，则构成完全图。

生成树

顶点和最小数量能连接这些顶点的边，构成生成树。

2 图的存储结构、遍历方式及最小生成树算法原理

2.1 图的存储结构

  • 邻接多重表，基于链表，用于无向图

有向图和无向图的存储结构有所不同，比如常用的存储结构

2.1.1 邻接矩阵

说明：基于数据，有向图、无向图均可。

权值
为弧赋于权值，为算法提供依据。

顶点

1
2
3
4
5
6
// 顶点
struct Node
{
	索引;
	数据;
};

弧或边的表示方法
说明：基于数组实现，实现简单，容易理解，用来实现边（无向图）或弧（有向图）。

有向图的邻接矩阵

无向图的邻接矩阵

1
2
3
4
5
6
// 图
struct Map
{
	顶点类型数组;
	邻接矩阵;// 二维数组
};

2.1.2 邻接表

说明：基于链表，用于有向图。邻接表有两类

  • 邻接表，和顶点关联的弧链表记录的是出弧信息
  • 逆邻接表，和顶点关联的弧链表记录的是入弧信息

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 顶点
struct Node
{
	顶点索引;
	该顶点出弧（邻接表）入弧（逆邻接表）链表头指针;
	顶点数据;
};

// 弧
struct Arc
{
	弧头（邻接表）或弧尾（逆邻接表）对应的顶点索引;
	当前节点另一条出弧（邻接表）或入弧（逆邻接表）的指针;
	弧信息（权值）;
};

// 图
struct Map
{
	顶点数据;
};

2.1.3 十字链表

说明：基于链表，用于有向图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 顶点
struct Node
{
	顶点索引;
	顶点数据;
	创建的第一条入弧指针;
	创建的第一条出弧指针;
};

// 弧
struct Arc
{
	弧头顶点索引;
	弧尾顶点索引;
	弧头相同的另一条弧的指针;
	弧尾相同的另一条弧的指针
	弧信息（权值）;
};

// 图
struct Map
{
	顶点数据;
};

2.1.4 邻接多重表

说明：基于链表，用于无向图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 边
struct Edge
{
	顶点 A 索引;
	顶点 B 索引;
	连接 A 的下一条边的指针;
	连接 B 的下一条边的指针;
};

// 顶点
struct Node
{
	顶点索引;
	顶点数据;
	第一条边节点指针;
};

// 图
struct Map
{
	顶点数组;
};

2.2 图的遍历

深度优先搜索

广度优先搜索

2.3 最小生成树

2.3.1 什么是最小生成树

使所有点连通的成本最小的边和点的集合构成最小生成树。如下，左边是图，右边是计算得到的最小生成树。

2.3.2 获取最小生成树

说明：常用的计算最小生成树的两个方法

普里姆 (Prim) 算法

把以当前选中的点为顶点的所有边作为下一步的待选边集合，选出待选边集合中权重最小的边，加入边集合，更新点集合。重复此步骤，直到所有点都进入了点集合。

通过下面的例子来说明。下面是计算的每一步骤。
（1）

（2）

（3）

（4）

（5）

克鲁斯卡尔 (Kruskal) 算法

把所有边都做为待选边集合，选出待选边集合中未选择的边中权重最小的边，加入边集合，更新点集合。重复此步骤，直到所有点都进入了点集合且点都连通在一起。

通过下面的例子来说明。下面是计算的每一步骤。
（1）

（2）

（3）

（4）

（5）

3 图的存储与遍历

C-PLUS-PLUS_STUDY/IMOOC_DATA_STRUCTOR_EXPLORE_CPP/l05_map/0301 at master · laputa-er/C-PLUS-PLUS_STUDY · GitHub

1
2
3
4
5
6
7
.
├── main.cpp
├── CMap.h
├── CMap.cpp
├── Node.h
├── Node.cpp
└── makefile

main.cpp

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
#include <iostream>
#include "CMap.h"
using namespace std;

int main(void)
{
	/*
	* 图的存储与遍历
	*
	* 1. 无向图
	* 2. 采用邻接矩阵（权值都为1）
	*
	*		 A
	*	   /   \
	*	  B      D
	*    / \    /  \
	*	C   F  G  - H
	*   \   /
	*     E
    *
	*      A B C D E F G H
	*
	*  A   0 1 0 1 0 0 0 0
	*  B   1 0 1 0 0 1 0 0
	*  C   0 1 0 0 1 0 0 0
	*  D   1 0 0 0 0 0 1 1
	*  E   0 0 1 0 0 1 0 0 
	*  F   0 1 0 0 1 0 0 0 
	*  G   0 0 0 1 0 0 0 1
	*  H   0 0 0 1 0 0 1 0
	*
	*/
	// 创建图
	CMap *pMap = new CMap(8);

	// 创建顶点顶点
	Node *pNodeA = new Node('A');
	Node *pNodeB = new Node('B');
	Node *pNodeC = new Node('C');
	Node *pNodeD = new Node('D');
	Node *pNodeE = new Node('E');
	Node *pNodeF = new Node('F');
	Node *pNodeG = new Node('G');
	Node *pNodeH = new Node('H');

	// 添加顶点
	pMap->addNode(pNodeA);
	pMap->addNode(pNodeB);
	pMap->addNode(pNodeC);
	pMap->addNode(pNodeD);
	pMap->addNode(pNodeE);
	pMap->addNode(pNodeF);
	pMap->addNode(pNodeG);
	pMap->addNode(pNodeH);

	// 设置邻接矩阵（无向图）
	pMap->setValueToMatrixForUndirectedGraph(0, 1);
	pMap->setValueToMatrixForUndirectedGraph(0, 3);
	pMap->setValueToMatrixForUndirectedGraph(1, 2);
	pMap->setValueToMatrixForUndirectedGraph(1, 5);
	pMap->setValueToMatrixForUndirectedGraph(3, 6);
	pMap->setValueToMatrixForUndirectedGraph(3, 7);
	pMap->setValueToMatrixForUndirectedGraph(6, 7);
	pMap->setValueToMatrixForUndirectedGraph(2, 4);
	pMap->setValueToMatrixForUndirectedGraph(4, 5);

	// 打印邻接矩阵
	pMap->printMatrix();
	cout << endl;

	pMap->resetNode();

	// 深度遍历
	pMap->depthFirstTraverse(0); // A B C E F D G H
	cout << endl;

	pMap->resetNode();

	// 广度遍历
	pMap->breadthFirstTraverse(0); // A B D C F G H E
	cout << endl;
	return 0;
}

CMap.h

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
#ifndef CMAP_H 
#define CMAP_H
#include "Node.h"
#include <vector>
using namespace std;
class CMap
{
public:
	CMap(int capacity);
	~CMap();
	bool addNode(Node *pNode);
	void resetNode(); // 重置顶点
	bool setValueToMatrixForDirectedGraph(int row, int col, int val = 1); // 为有向图设置邻接矩阵
	bool setValueToMatrixForUndirectedGraph(int row, int col, int val = 1); // 为无向图设置邻接矩阵
	void printMatrix(); // 打印邻接矩阵
	void depthFirstTraverse(int nodeIndex); // 深度优先遍历
	void breadthFirstTraverse(int nodeIndex); // 广度优先遍历
private:
	bool getValueFromMatrix(int row, int col, int &val); // 从矩阵中获取权值
	void breadthFirstTraverseImpl(vector<int> preVec); // 广度优先遍历实现函数
private:
	int m_iCapacity; // 图中最多容纳的顶点数
	int m_iNodeCount; // 已经添加的顶点（节点）的个数
	Node *m_pNodeArray; // 用来存放顶点数组
	int *m_pMatrix; // 用来存放邻接矩阵
};
#endif

CMap.cpp

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
177
178
179
180
#include <iostream>
#include "CMap.h"
#include <vector>

using namespace std;

CMap::CMap(int capacity)
{
	m_iCapacity = capacity;
	m_iNodeCount = 0; // 已经设置的当前顶点数量
	m_pNodeArray = new Node[m_iCapacity]; // 为顶点数组分配内存
	m_pMatrix = new int[m_iCapacity * m_iCapacity]; // 为邻接矩阵分配内存
	memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int)); // 初始化邻接矩阵每个元素的值为0
}
CMap::~CMap()
{
	delete []m_pNodeArray;
	delete []m_pMatrix;
	m_pNodeArray = NULL;
	m_pMatrix = NULL;
}

bool CMap::addNode(Node *pNode)
{
	m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;
	m_iNodeCount++;
	return true;
}

void CMap::resetNode()
{
	for(int i = 0; i < m_iNodeCount; i++)
	{
		m_pNodeArray[i].m_bIsVisited = false;
	}
}

bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val)
{
	if(row < 0 || row >= m_iCapacity)
	{
		return false;
	}
	if(col < 0 || col >= m_iCapacity)
	{
		return false;
	}
	m_pMatrix[row * m_iCapacity + col] = val;
	return true;
}

bool CMap::setValueToMatrixForUndirectedGraph(int row, int col, int val)
{
	if(row < 0 || row >= m_iCapacity)
	{
		return false;
	}
	if(col < 0 || col >= m_iCapacity)
	{
		return false;
	}
	m_pMatrix[row * m_iCapacity + col] = val;
	m_pMatrix[col * m_iCapacity + row] = val;
	return true;
}

void CMap::printMatrix()
{
	for(int i = 0; i < m_iCapacity; i++)
	{
		for(int k = 0; k < m_iCapacity; k++)
		{
			cout << m_pMatrix[i * m_iCapacity + k] << " ";
		}
		cout << endl;
	}
}

bool CMap::getValueFromMatrix(int row, int col, int &val)
{
	if(row < 0 || row >= m_iCapacity)
	{
		return false;
	}
	if(col < 0 || col >= m_iCapacity)
	{
		return false;
	}
	val = m_pMatrix[row * m_iCapacity + col];
	return true;
}

/*
* 深度优先遍历
* 遍历一遍所有节点，并把遍历过的节点的 m_bIsvisited 属性设置为 true
* @param{int} nodeIndex 遍历的起点
*/
void CMap::depthFirstTraverse(int nodeIndex)
{
	int value = 0;
	cout << m_pNodeArray[nodeIndex].m_cData << " ";
	m_pNodeArray[nodeIndex].m_bIsVisited = true;
	// 从邻接矩阵中寻找和当前节点存在连接的节点
	for(int i = 0; i < m_iCapacity; i++)
	{
		// 读取邻接矩阵中的值
		getValueFromMatrix(nodeIndex, i, value);
		// 存在连线, 也就意味着找到了一个节点，其下标为 i
		if(value != 0)
		{
			if(m_pNodeArray[i].m_bIsVisited)
			{
				continue;
			}
			else
			{
				depthFirstTraverse(i);
			}
		}
		else
		{
			continue;
		}
	}
}

/*
* 广度优先遍历
*/
void CMap::breadthFirstTraverse(int nodeIndex)
{
	cout << m_pNodeArray[nodeIndex].m_cData << " ";
	m_pNodeArray[nodeIndex].m_bIsVisited = true;
	vector<int> curVec;
	curVec.push_back(nodeIndex);
	// 依次遍历当前 curVec 中的节点所有的子节点
	breadthFirstTraverseImpl(curVec);
}

/*
* 依次遍历指定节点下标集合中所有节点的字节点
*/
void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
	int value = 0;
	// 声明下一层节点下标集合
	vector<int> curVec;

	// 遍历上一层节点下标集合
	for(int j = 0; j < (int)preVec.size(); j++)
	{
		// 通过邻接矩阵寻找邻接点
		for(int i = 0; i < m_iCapacity; i++)
		{
			// 获取邻接矩阵中的值
			getValueFromMatrix(preVec[j], i, value);
			if(value != 0)
			{
				if(m_pNodeArray[i].m_bIsVisited)
				{
					continue;
				}
				else
				{
					cout << m_pNodeArray[i].m_cData << " ";
					m_pNodeArray[i].m_bIsVisited = true;
					curVec.push_back(i);
				}
			}
			else
			{
				continue;
			}
		}
	}
	if(curVec.size() > 0)
	{
		breadthFirstTraverseImpl(curVec);
	}
}

Node.h

1
2
3
4
5
6
7
8
9
10
11
12
#ifndef NODE_H
#define NODE_H

class Node
{
public:
	Node(char data = 0);
	char m_cData; // 当前节点的数据
	bool m_bIsVisited; // 当前节点有没有被访问过
};

#endif

Node.cpp

1
2
3
4
5
6
#include "Node.h"
Node::Node(char data)
{
	m_cData = data;
	m_bIsVisited = false;
}

4 图的最小生成树算法

C-PLUS-PLUS_STUDY/IMOOC_DATA_STRUCTOR_EXPLORE_CPP/l05_map/0401_min_tree at master · laputa-er/C-PLUS-PLUS_STUDY · GitHub

1
2
3
4
5
6
7
8
9
.
├── CMap.h
├── CMap.cpp
├── Edge.h
├── Edge.cpp
├── Node.h
├── Node.cpp
├── main.cpp
└── makefile

main.cpp

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
#include <iostream>
#include “CMap.h”
using namespace std;

int main(void)
{
	/*
	* 图的存储与遍历
	*
	* 1. 无向图
	* 2. 采用邻接矩阵（权值都为1）
	*
	* 图示
	*		 A
	*	   / |  \
	*	 B - F - E
	*    \  / \  /
	*	  C  - D
    *
	* 节点
	*  A B C D E F
	*  0 1 2 3 4 5
	*
	* 邻接矩阵
	*      A B C D E F
	*
	*  A   0 6 0 0 5 1
	*  B   6 0 3 0 0 2
	*  C   0 3 0 7 0 8
	*  D   0 0 7 0 2 4
	*  E   5 0 0 2 0 9
	*  F   1 2 8 4 9 0 
	*
	*/
	// 创建图
	CMap *pMap = new CMap(6);

	// 创建顶点顶点
	Node *pNodeA = new Node(‘A’);
	Node *pNodeB = new Node(‘B’);
	Node *pNodeC = new Node(‘C’);
	Node *pNodeD = new Node(‘D’);
	Node *pNodeE = new Node(‘E’);
	Node *pNodeF = new Node(‘F’);

	// 添加顶点
	pMap->addNode(pNodeA);
	pMap->addNode(pNodeB);
	pMap->addNode(pNodeC);
	pMap->addNode(pNodeD);
	pMap->addNode(pNodeE);
	pMap->addNode(pNodeF);

	// 设置邻接矩阵（无向图）
	pMap->setValueToMatrixForUndirectedGraph(0, 1, 6);
	pMap->setValueToMatrixForUndirectedGraph(0, 4, 5);
	pMap->setValueToMatrixForUndirectedGraph(0, 5, 1);
	pMap->setValueToMatrixForUndirectedGraph(1, 2, 3);
	pMap->setValueToMatrixForUndirectedGraph(1, 5, 2);
	pMap->setValueToMatrixForUndirectedGraph(2, 5, 8);
	pMap->setValueToMatrixForUndirectedGraph(2, 3, 7);
	pMap->setValueToMatrixForUndirectedGraph(3, 5, 4);
	pMap->setValueToMatrixForUndirectedGraph(3, 4, 2);
	pMap->setValueToMatrixForUndirectedGraph(4, 5, 9);

	// 打印邻接矩阵
	pMap->printMatrix();
	cout << endl;

	pMap->resetNode();

	// 深度遍历
	pMap->depthFirstTraverse(0); // A B C E F D G H
	cout << endl;

	pMap->resetNode();

	// 广度遍历
	pMap->breadthFirstTraverse(0); // A B D C F G H E
	cout << endl << endl;
	
	pMap->resetNode();
	
	// 获取最小生成树(普里姆算法)
	pMap->primTree(0); // A-F F-B B-C F-D D-E
	
	// 获取最小生成树(普里姆算法)
	pMap->kruskalTree();
	return 0;
}

CMap.h

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
#ifndef CMAP_H 
#define CMAP_H
#include <vector>
#include "Node.h"
#include "Edge.h"
using namespace std;
class CMap
{
public:
	CMap(int capacity);
	~CMap();
	bool addNode(Node *pNode);
	void resetNode(); // 重置顶点
	bool setValueToMatrixForDirectedGraph(int row, int col, int val = 1); // 为有向图设置邻接矩阵
	bool setValueToMatrixForUndirectedGraph(int row, int col, int val = 1); // 为无向图设置邻接矩阵
	void printMatrix(); // 打印邻接矩阵
	void depthFirstTraverse(int nodeIndex); // 深度优先遍历
	void breadthFirstTraverse(int nodeIndex); // 广度优先遍历
	void primTree(int nodeIndex); // 通过普里姆算生成最小生成树
	void kruskalTree(); // 克鲁斯卡尔算法生成最小生成树
private:
	int getMinEdge(vector<Edge> edgeVec); // 获取边集合中还没被选择的权值最小的边
	bool getValueFromMatrix(int row, int col, int &val); // 从矩阵中获取权值
	void breadthFirstTraverseImpl(vector<int> preVec); // 广度优先遍历实现函数
	bool isInSet(vector<int> nodeSet, int target); // 判断某个值是否在某个 vector 当中
	void mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB); // 将 nodeSetB 合并 nodeSetB
	
private:
	int m_iCapacity; // 图中最多容纳的顶点数
	int m_iNodeCount; // 已经添加的顶点（节点）的个数
	Node *m_pNodeArray; // 用来存放顶点数组
	int *m_pMatrix; // 用来存放邻接矩阵
	Edge *m_pEdge; // 已选边集合
};

#endif

CMap.cpp

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
#include <iostream>
#include "CMap.h"
#include <vector>

using namespace std;

CMap::CMap(int capacity)
{
	m_iCapacity = capacity;
	m_iNodeCount = 0; // 已经设置的当前顶点数量
	m_pNodeArray = new Node[m_iCapacity]; // 为顶点数组分配内存
	m_pMatrix = new int[m_iCapacity * m_iCapacity]; // 为邻接矩阵分配内存
	memset(m_pMatrix, 0, m_iCapacity * m_iCapacity * sizeof(int)); // 初始化邻接矩阵每个元素的值为0

	m_pEdge = new Edge[m_iCapacity - 1]; // 最小生成树的边的数量为顶点的数量-1
}
CMap::~CMap()
{
	delete []m_pNodeArray;
	delete []m_pMatrix;
	delete []m_pEdge;
	m_pNodeArray = NULL;
	m_pMatrix = NULL;
}

bool CMap::addNode(Node *pNode)
{
	m_pNodeArray[m_iNodeCount].m_cData = pNode->m_cData;
	m_iNodeCount++;
	return true;
}

void CMap::resetNode()
{
	for(int i = 0; i < m_iNodeCount; i++)
	{
		m_pNodeArray[i].m_bIsVisited = false;
	}
}

bool CMap::setValueToMatrixForDirectedGraph(int row, int col, int val)
{
	if(row < 0 || row >= m_iCapacity)
	{
		return false;
	}
	if(col < 0 || col >= m_iCapacity)
	{
		return false;
	}
	m_pMatrix[row * m_iCapacity + col] = val;
	return true;
}

bool CMap::setValueToMatrixForUndirectedGraph(int row, int col, int val)
{
	if(row < 0 || row >= m_iCapacity)
	{
		return false;
	}
	if(col < 0 || col >= m_iCapacity)
	{
		return false;
	}
	m_pMatrix[row * m_iCapacity + col] = val;
	m_pMatrix[col * m_iCapacity + row] = val;
	return true;
}

void CMap::printMatrix()
{
	for(int i = 0; i < m_iCapacity; i++)
	{
		for(int k = 0; k < m_iCapacity; k++)
		{
			cout << m_pMatrix[i * m_iCapacity + k] << " ";
		}
		cout << endl;
	}
}

bool CMap::getValueFromMatrix(int row, int col, int &val)
{
	if(row < 0 || row >= m_iCapacity)
	{
		return false;
	}
	if(col < 0 || col >= m_iCapacity)
	{
		return false;
	}
	val = m_pMatrix[row * m_iCapacity + col];
	return true;
}

/*
* 深度优先遍历
* 遍历一遍所有节点，并把遍历过的节点的 m_bIsvisited 属性设置为 true
* @param{int} nodeIndex 遍历的起点
*/
void CMap::depthFirstTraverse(int nodeIndex)
{
	int value = 0;
	cout << m_pNodeArray[nodeIndex].m_cData << " ";
	m_pNodeArray[nodeIndex].m_bIsVisited = true;
	// 从邻接矩阵中寻找和当前节点存在连接的节点
	for(int i = 0; i < m_iCapacity; i++)
	{
		// 读取邻接矩阵中的值
		getValueFromMatrix(nodeIndex, i, value);
		// 存在连线, 也就意味着找到了一个节点，其下标为 i
		if(value != 0)
		{
			if(m_pNodeArray[i].m_bIsVisited)
			{
				continue;
			}
			else
			{
				depthFirstTraverse(i);
			}
		}
		else
		{
			continue;
		}
	}
}

/*
* 广度优先遍历
*/
void CMap::breadthFirstTraverse(int nodeIndex)
{
	cout << m_pNodeArray[nodeIndex].m_cData << " ";
	m_pNodeArray[nodeIndex].m_bIsVisited = true;
	vector<int> curVec;
	curVec.push_back(nodeIndex);
	// 依次遍历当前 curVec 中的节点所有的子节点
	breadthFirstTraverseImpl(curVec);
}

/*
* 依次遍历指定节点下标集合中所有节点的字节点
*/
void CMap::breadthFirstTraverseImpl(vector<int> preVec)
{
	int value = 0;
	// 声明下一层节点下标集合
	vector<int> curVec;

	// 遍历上一层节点下标集合
	for(int j = 0; j < (int)preVec.size(); j++)
	{
		// 通过邻接矩阵寻找邻接点
		for(int i = 0; i < m_iCapacity; i++)
		{
			// 获取邻接矩阵中的值
			getValueFromMatrix(preVec[j], i, value);
			if(value != 0)
			{
				if(m_pNodeArray[i].m_bIsVisited)
				{
					continue;
				}
				else
				{
					cout << m_pNodeArray[i].m_cData << " ";
					m_pNodeArray[i].m_bIsVisited = true;
					curVec.push_back(i);
				}
			}
			else
			{
				continue;
			}
		}
	}
	if(curVec.size() > 0)
	{
		breadthFirstTraverseImpl(curVec);
	}
}

// 普里姆算法生成最小生成树
void CMap::primTree(int nodeIndex)
{
	int value = 0; // 临时存放从临界矩阵中获取的权值
	int edgeCount = 0; // 获得的边的数量
	vector<Edge> edgeVec; // 边的集合
	vector<int> nodeVec; // 下一个要
	nodeVec.push_back(nodeIndex);
	m_pNodeArray[nodeIndex].m_bIsVisited = true;

	// 如果顶点的数量为 N ，最小生成树边的数量就是 N -1，以此作为循环的终止条件
	while(edgeCount < m_iCapacity -1)
	{
		int temp = nodeVec.back();
		// 找到所有的备选边
		// 遍历出和下标为 temp 的顶点有连线的点
		for(int i = 0; i < m_iCapacity; i++)
		{
			getValueFromMatrix(temp, i, value);

			if(value != 0)
			{
				// 如果下一个点被选择了，就跳过
				if(m_pNodeArray[i].m_bIsVisited)
				{
					continue;
				}
				else
				{
					// 在已选边集合中添加一个新的边
					Edge edge(temp, i, value);
					edgeVec.push_back(edge);
				}
			}
		}
		// 从可选边集合中找出最小的边
		int edgeIndex = getMinEdge(edgeVec);
		edgeVec[edgeIndex].m_bSelected = true;

		cout << m_pNodeArray[edgeVec[edgeIndex].m_iNodeIndexA].m_cData << "-" << m_pNodeArray[edgeVec[edgeIndex].m_iNodeIndexB].m_cData << " ";

		// 将这次找到的最小边放入到集合中
		m_pEdge[edgeCount] = edgeVec[edgeIndex];
		edgeCount++;

		// 通过找到的边拿到新发现的点
		int nextNodeIndex = edgeVec[edgeIndex].m_iNodeIndexB;
		nodeVec.push_back(nextNodeIndex);
		m_pNodeArray[nextNodeIndex].m_bIsVisited = true; // 设置,点被选择了
	}
	cout << endl;
}

// 从待选边中找到权值最小的边
int CMap::getMinEdge(vector<Edge> edgeVec)
{
	int minWeight = 0; // 最小边的权值
	int edgeIndex = 0; // 最小边的下标

	// 找到还没选择的边中最小的
	for(int i = 0; i < edgeVec.size(); i++)
	{
		if(!edgeVec[i].m_bSelected)
		{
			if(minWeight == 0)
			{
				minWeight = edgeVec[i].m_iWeightValue;
			}
			else if(minWeight > edgeVec[i].m_iWeightValue)
			{
				minWeight = edgeVec[i].m_iWeightValue;
				edgeIndex = i;
			}
		}
	}
	// 所有的边都已经被选过了，因此没有最小边
	if(minWeight == 0)
	{
		return -1;
	}
	return edgeIndex;
}

void CMap::kruskalTree()
{
	int value = 0;
	int edgeCount = 0;
	// 定义存放节点集合的数组
	vector< vector<int> >nodeSets;

	// 第一步：取出所有的边
	vector<Edge> edgeVec;
	// 只遍历临邻接矩阵上半部分就足够了
	for(int i = 0; i < m_iCapacity; i++)
	{
		for(int k = i + 1; k < m_iCapacity; k++)
		{
			getValueFromMatrix(i, k, value);
			if(value != 0)
			{
				Edge edge(i, k, value);
				edgeVec.push_back(edge);
			}
		}
	}

	// 第二步：从所有边中取出组成最小生成树的边
	// 1. 找到算法的结束条件
	while(edgeCount < m_iCapacity - 1)
	{
		// 2. 从边集合中找到最小边
		int minEdgeIndex = getMinEdge(edgeVec);
		edgeVec[minEdgeIndex].m_bSelected = true;
		
		// 3. 找出最小边连接的点
		int nodeAIndex = edgeVec[minEdgeIndex].m_iNodeIndexA;
		int nodeBIndex = edgeVec[minEdgeIndex].m_iNodeIndexB;

		// 4. 找出点所在的点集合
		bool nodeAIsInSet = false;
		bool nodeBIsInSet = false;
		int nodeAInSetLabel = -1; // A 端所在的点集合下标
		int nodeBInSetLabel = -1; // B 端所在的点集合下标
		// 获取 A 端所在的点集合下标（如果找到的话）
		for(int i = 0; i < nodeSets.size(); i++)
		{
			nodeAIsInSet = isInSet(nodeSets[i], nodeAIndex);
			if(nodeAIsInSet)
			{
				nodeAInSetLabel = i;
			}
		}
		// 获取 B 端所在的点集合下标（如果找到的话）
		for(int i = 0; i < nodeSets.size(); i++)
		{
			nodeBIsInSet = isInSet(nodeSets[i], nodeBIndex);
			if(nodeBIsInSet)
			{
				nodeBInSetLabel = i;
			}
		}
		// 5. 根据点所在集合的不同做出不同处理
		// 两个端点都不在已有集合中
		if(nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
		{
			vector<int> vec;
			vec.push_back(nodeAIndex);
			vec.push_back(nodeBIndex);
			nodeSets.push_back(vec);
		}
		// A 不在某个集合中， B 在某个集合中
		else if(nodeAInSetLabel == -1 && nodeBInSetLabel != -1)
		{
			nodeSets[nodeBInSetLabel].push_back(nodeAIndex);
		}
		// A 在某个集合中， B 不在某个集合中
		else if(nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
		{
			nodeSets[nodeAInSetLabel].push_back(nodeBIndex);
		}
		// A 和 B 分别在两个不同的集合中
		else if(nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBIsInSet)
		{
			// 将 B 所在的集合合并到 A 所在的集合
			mergeNodeSet(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]);
			// 把原来的 B 集合清除掉
			for(int k = nodeBInSetLabel; k < (int)nodeSets.size(); k++)
			{
				nodeSets[k] = nodeSets[k + 1];
			}
		}
		// 如果 A、B 本来已经都在同一个集合中了，那么再连线就成了回路，因此要把这条边放弃掉
		else if(nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBIsInSet)
		{
			continue;
		}
		
		// 6. 最后把新确定的一条边添加进最小生成树集合
		m_pEdge[edgeCount] = edgeVec[minEdgeIndex];
		edgeCount++;

		cout << edgeVec[minEdgeIndex].m_iNodeIndexA << "-" << edgeVec[minEdgeIndex].m_iNodeIndexB << " ";
		cout << edgeVec[minEdgeIndex].m_iWeightValue << endl;
	}
}

bool CMap::isInSet(vector<int> nodeSet, int target)
{
	for(int i = 0; i < nodeSet.size(); i++)
	{
		if(nodeSet[i] == target)
		{
			return true;
		}
	}
	return false;
}

void CMap::mergeNodeSet(vector<int> &nodeSetA, vector<int> nodeSetB)
{
	for(int i = 0; i < nodeSetB.size(); i++)	
	{
		nodeSetA.push_back(nodeSetB[i]);
	}
}

Edge.h

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef EDGE_H
#define EDGE_H

class Edge
{
public:
	Edge(int nodeIndexA = 0, int nodeIndexB = 0, int weightValue = 0);
	int m_iNodeIndexA; // 端点 A 的顶点下标
	int m_iNodeIndexB; // 端点 B 的顶点下标
	int m_iWeightValue; // 权值
	bool m_bSelected; // 是否已经被选择
};
#endif

Edge.cpp

1
2
3
4
5
6
7
8
9
#include "Edge.h"

Edge::Edge(int nodeIndexA, int nodeIndexB, int weightValue)
{
	m_iNodeIndexA = nodeIndexA;
	m_iNodeIndexB = nodeIndexB;
	m_iWeightValue = weightValue;
	m_bSelected = false;
}

Node.h

1
2
3
4
5
6
7
8
9
10
11
12
#ifndef NODE_H
#define NODE_H

class Node
{
public:
	Node(char data = 0);
	char m_cData; // 当前节点的数据
	bool m_bIsVisited; // 当前节点有没有被访问过
};

#endif

Node.cpp

1
2
3
4
5
6
#include "Node.h"
Node::Node(char data)
{
	m_cData = data;
	m_bIsVisited = false;
}