数据结构之图算法

图在数据结构中表示的是多对多的关系,这部分内容总结了数据结构中常用的图算法。


概念

  • 有向图:之间只具有单向关系的顶点构成的图称为有向图。
  • 无向图:之间具有双向关系的顶点构成的图称为无向图。
  • 完全图 :对于无向图来说,如果图中每个顶点都和除自身之外的所有顶点有关系,那么就称这样的无向图为完全图。
  • 入度:在有向图中,对于一个顶点 v 来说,箭头指向顶点 v 的弧的数目为该顶点的入度。
  • 出度:箭头远离顶点 v 的弧的数目为该顶点的出度。
  • 路径 :在图中从一个顶点到另一个顶点所走过的多个顶点组成的序列,就称为“路径”。
  • 回路:在有向图中,路径是有向的。如果在路径中第一个顶点和最后一个顶点相同,此路径称为“回路”或“环”。
  • 连通图:在无向图中,如果一个顶点到另一个顶点存在至少一条路径,称它们之间是连通的。 如果图中任意两个顶点之间都是连通的,则此图为连通图。
  • 生成树:对于连通图来说,如果对其进行遍历,遍历过程中经过的顶点和边其实质是一棵树,在这里称之为“生成树”。

    由于连通图中,任意两顶点之间可能含有多条通路,所以一个连通图可能会对应多个生成树。


图的表示方法

数组

在使用二维数组存储图中顶点之间的关系时,如果顶点之间存在边或弧,在相应位置用 1 表示,反之用 0 表示;如果使用二维数组存储网中顶点之间的关系,顶点之间如果有边或者弧的存在,在数组的相应位置存储其权值;反之用 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
struct Node {
int id;
vector<Node *> neighbors;
Node(int id) : id(id) {}
Node() {}
};
void bfs(Node *root) {
queue<Node *> q;
map<Node *, bool> visited;
q.push(root);
visited[root] = true;
while (!q.empty()) {
Node *node = q.front();
cout << node->id << " ";
q.pop();
for (vector<Node *>::iterator it = node->neighbors.begin(); it != node->neighbors.end();
++it) {
if (!visited.count(*it)) {
visited[*it] = true;
q.push(*it);
}
}
}
cout << endl;
}


DFS

图的深度优先遍历(DFS)类似树的前序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(Node *root) {
if (visited.count(root)) return;
visited[root] = true;
cout << root->id << " ";
for (vector<Node *>::iterator it = root->neighbors.begin(); it != root->neighbors.end();
++it) {
dfs(*it);
}
}


最小生成树(MST)

Prim算法

其基本思想是,寻找这样的边:满足“一个点在生成树中,一个点不在生成树中”的边中权值最小的一条边。将找到的边加入边集中,顶点加到顶点集中,当所有顶点都加入进来时,算法结束。
Prim算法

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
const int MaxVertex = 100;
struct EdgeType {
int lowcost;
int adjvex;
};
struct Graph {
int arc[MaxVertex][MaxVertex];
int vertexNum;
};
int MinEdge(EdgeType shortEdge[], int vertenNum) {
int minEdge = INT8_MAX;
for (int i=0; i<vertenNum; ++i) {
if (shortEdge[i].adjvex != 0 && minEdge < shortEdge[i].lowcost) {
minEdge = i;
}
}
return minEdge;
}
void Prim(Graph G) {
EdgeType *shortEdge = new EdgeType[G.vertexNum];
for (int i=1; i<G.vertexNum; ++i) {
shortEdge[i].lowcost = G.arc[0][i];
shortEdge[i].adjvex = 0;
}
shortEdge[0].lowcost = 0;
for(int i=1; i<G.vertexNum; ++i) {
int k = MinEdge(shortEdge, G.vertexNum);
cout << '(' << k << ')' << shortEdge[k].adjvex << ')' << endl;
shortEdge[k].lowcost = 0;
for (int j=1; j<G.vertexNum; ++j) {
if (G.arc[k][j] < shortEdge[j].lowcost) {
shortEdge[j].lowcost = G.arc[k][j];
shortEdge[j].adjvex = k;
}
}
}
}

Prim算法的时间复杂度为O(n^2),与图中的边数无关,适合求稠密图的最小生成树。


Kruskal算法

其基本思想是:每次从未标记的边中选取最小权值的边,如果该边的两个顶点位于两个不同的连通分量,则将该边加入最小生成树,合并两个连通分量,并标记该边。否则,位于同一个连通分量,则去掉该边(同样标记即可),避免造成回路。
Prim算法

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
const int MaxVertex = 10;
const int MaxEdge = 100;
struct EdgeType
{
int from, to;
int weight;
};
struct EdgeGraph
{
int vertex[MaxVertex];
EdgeType edge[MaxEdge];
int vertexNum, edgeNum;
};
int FindRoot(int parent[], int v) {
int t = v;
if (parent[t]!=-1) t = parent[t];
return t;
}
void Kruskal(EdgeGraph G) {
int *parent = new int[G.vertexNum];
for (int i=0; i<G.vertexNum; ++i) {
parent[i] = -1;
}
for (int num=0, i=0; i<G.edgeNum; ++i) {
int v1 = FindRoot(parent, G.edge[i].from);
int v2 = FindRoot(parent, G.edge[i].to);
if (v1 != v2) {
cout << '(' << v1 << ',' << v2 << ')' << endl;
parent[v2] = v1;
num++;
if(num == G.vertexNum-1) return;
}
}
}


最短路径

Dijkstra算法

Dijkstra算法
Dijkstra算法使用贪心策略,每一次添加一条边就更新顶点的最短路径值,贪心策略为每次选取值最小的点。Dijkstra用来求一个点到其余各点的最短距离,也叫做“单源最短距离”。

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
const int MaxNum = 10;
int A[MaxNum][MaxNum];
void Dijkstra(int v, int n) {
int dist[MaxNum];
int visited[MaxNum];
for (int i=1; i<=n; ++i) {
dist[i] = A[v][i];
visited[i] = 0;
}
visited[v] = 1;
for (int i=1; i<=n-1; ++i) {
int minDis = INT8_MIN;
int index;
for (int j=1; j<=n; ++j) {
if (visited[j] == 0 && dist[j] < minDis) {
minDis = dist[j];
index = j;
}
}
visited[index] = 1;
for (int j=1; j<=n; ++j) {
if (dist[j] > dist[index]+A[index][j]) {
dist[j] = dist[index]+A[index][j];
}
}
}
}


Floyd算法

Floyd用来计算图中任意一点到其他点的最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int MaxNum = 10;
int A[MaxNum][MaxNum];
void Dijkstra(int v, int n) {
for(int k=1; k<=n; ++k) {
for (int i=1; i<=n; ++i) {
for (int j=1; j<=n; ++j) {
if (A[j][j] > A[i][k]+A[k][j]) {
A[i][j] = A[i][k]+A[k][j];
}
}
}
}
}

参考文献:
最小生成树-MST算法详解及代码实现
【每日算法】图算法(遍历&MST&最短路径&拓扑排序)
【坐在马桶上看算法】算法7:Dijkstra最短路算法
【坐在马桶上看算法】算法6:只有五行的Floyd最短路算法