这部分为了快速入坑参考了浙大的课程，邓俊辉那个由于自己 C++
基础太拉胯了就换了个简单的
www。后面还有一些细节的地方懒得搞了，反正写了这文章也图一乐
2333333，以后再润色了（
「re:
从零开始的带学数据结构㈡」图的一点基础理解
图的相关定义
概论
线性表和树本身是图的特殊情形。线性表和树表示的是一对一和一对多的关系，而图表示的是多对多的关系。包含：
一组顶点（Vertex）
一组边（Edge）
其中：
边是顶点对， (v, w) ∈ E，其中 v, w ∈ V；
有向边 <v, w> 表示从 v 指向 w 的边（单行线）；
不考虑自回路
简单路径：不经过相同的顶点。
邻接：顶点和顶点
关联：顶点和边
ADT
表示方法
邻接矩阵
G [N] [N]，N 个顶点从 0 到 N-1 编号。
- 注意：二维数组的顺序是
A [X] [Y]。分别代表 X 位置和 Y
位置。
其中 G [I] [J] = 1，若 <vi, vj>是 G
中的边；否则是 0.
直观。方便找邻接点、边、计算度（出度、入度）。但面对稀疏图的时候会浪费空间。
邻接表
G [N] 是指针数组，对应矩阵每行一个链表，只存非 0 元素。
节约稀疏图的空间、便于计算出度。但不便检查顶点间的边、也不便计算入度。
图的遍历
广度优先搜索（BFS）
一套矩阵图的 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
|
void BFS(Vertex S)
{
queue<Vertex> Q;
Vertex Temp;
cout << MGraph->Elements[S] << endl;
MGraph->Visited[S] = true;
Q.push(S);
while(!Q.empty())
{
Temp = Q.front();
Q.pop();
for(int i = 0; i < MGraph->Vertex_Amount; i++)
{
if(MGraph->WeightContainer[Temp][i] != INFINITY && !MGraph->Visited[i])
{
cout << MGraph->Elements[i] << endl;
MGraph->Visited[i] = true;
Q.push(i);
}
}
}
}
|
深度优先搜索（DFS）
伪代码实现：
1
2
3
4
5
6
7
8
| void DFS(Vertex V)
{
V.visited = true;
for(iterator in adjvexs of V)
{
DFS(V.adjvex);
}
}
|
最短路径问题
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的一条路径。这条路径（源点
- 终点）的路径就是最短路径。
分为：
- 单源：对从某固定源点出发，到其他顶点
- 多源：任意两顶点。
单源带权图最短路径问题——Dijkstra
算法（视频理解）
前提
给定两个数组 Distance 和 Previous
来表示目标点到不同点的距离，以及达到这个路径需要走的前一个节点。
过程
初始化：先利用 flag 标记源点（下例表示为
V0），代表收入到最短路线集合里面；并且计算 V0 到邻接点的距离，存入
Distance 数组内，上一个元素显然是 V0，故存入 Previous 中。
循环开始：每次找未标记的节点里面距离出发点最近（Distance
最小）的节点。标记、收录到最短路线集合里面。
计算它到邻接点的距离，如果端点 P 和邻接点 A 之间满足： \[
Dist[A] < Dist[P] + Edge<P, A>
\] 那么就把邻接点的 Distance[A] 和 Previous[A] 更新。（松弛）
每步取最优的操作是贪心算法思想的体现。
实现
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
|
Vertex FindMinDistance(GNode* G, int distance[], bool collected[])
{
Vertex MinPosition;
int MinDist = INFINITY;
for(int i = 0; i < G->Vertex_Amount; i++)
{
if(collected[i] == false && distance[i] < MinDist)
{
MinDist = distance[i];
MinPosition = i;
}
}
if(MinDist < INFINITY)
return MinPosition;
else
return -1;
}
void Dijkstra(GNode* G, int distance[], int previous[], Vertex S)
{
bool collected[MaxVertexNum] = {false};
previous = {-1};
distance = {INFINITY};
distance[S] = 0;
collected[S] = true;
while(1)
{
Vertex V = FindMinDistance(G, distance, collected);
if(V==-1)
break;
collected[V] = true;
for(Vertex W = 0; W < G->Vertex_Amount; W++)
{
if(collected[W] == false && G->WeightContainer[V][W] < INFINITY)
{
if(distance[V] + G->WeightContainer[V][W] < distance[W])
{
distance[W] = distance[V] + G->WeightContainer[V][W];
previous[W] = V;
}
}
}
}
}
|
多源最短路算法——Floyd 算法
前提
调用 V 次 Dijkstra
之类的算法也可以暴力解决多源最短路算法。它的时间复杂度是
O(V^3 + V*E)，但只在稀疏图可以实现 Floyd 算法的程度，达到
O(V^3) 的水平。
过程
代码实现
最小生成树
前提
树：无回路，边比顶点少一个。
生成：包含所有顶点，边都在图内。
权重和最小。
最小生成树存在，图一定联通。
算法分析
贪心算法可以在这个问题应用：
- 每一步取最优结果——代表权重最小的边
- 约束情况：只能用图中的边、正好用掉 V-1 条、不能有回路
方法 1：Prim 算法
Prim
算法的基本思路是：从一个根节点开始，慢慢地建立起一棵树。每次选权重最小的来生成。如果最后节点数量不够，就说明图不连通，生成失败。
伪代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void Prim()
{
MST = {s}; //最小生成树
while(1)
{
V = 最小 dist;
if 不存在，break;
将 V 收录到 MST：dist[V] = 0
for(V 的每个邻接点 W)
if(dist[W]!=0)
{
if E(V,W) < dist[W]
dist[W] = E(V,W)
parent[W] = V;
}
}
if MST 顶点不够 V 个
error（生成树不存在）
}
|
