第五章图
邻接矩阵
基本思想：vexNum表示顶点数量，arcNum表示边数量，edges表示边（1或者权值）
1
2
3
4
| struct MGraph{
int edge[Maxn][Maxn];
int vexNum,arcNum;
};
|
邻接表
1
2
3
4
5
6
7
8
9
10
11
12
| struct ArcNode{
int adjvex;
ArcNode *next;
};
struct VNode{
int data;
ArcNode *firstarc;
};
struct AGraph{
VNode adjlist[Maxn];
int vexNum,arcNum;
};
|
图的遍历
图的深度优先遍历
思想:
1.首先，访问开始结点从起始结点开始任选一个相邻并未被访问的结点，访问；
2.接着，把找到的结点作为起始结点继续访问其相邻且未被访问的一个结点;
3.重复 2 的操作直到某一个结点所有相邻结点都被访问，则退回最近被访问且还有相邻结点 未被访问的结点；
4.把 3 中结点作为起始结点继续执行 2，3 操作直到所有结点都被访问完为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void visit(int x){
cout << x << "\t";
}
void DFS(AGraph *g,int v,int vis[]){
ArcNode *p;
vis[v] = 1;
visit(v);
p = g->adjlist[v].firstarc;
while(p != NULL){
if(vis[p->adjvex != 1])
DFS(g,p->adjvex, vis);
p = p->next;
}
}
|
图的广度优先遍历
思想：
1.首先，从起始结点出发访问其所有相邻的且未被访问的结点，并把访问的结点入队；
2.接着，当队列不为空时候队首元素出队并将其作为起始结点执行 1 操作;
3.最后重复执行 2 操作直到队列为空或者所有结点都访问完毕为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void BFS(AGraph *g,int v,int vis[]){
int que[Maxn];
int front = rear = -1;
visit(v);
vis[v] = 1;
que[++rear] = v;
ArcNode *p;
while(front < rear){
int k = que[++front];
p = g->adjlist[k].firstarc;
while(p != NULL){
if(vis[p->adkvex] == 0){
que[++rear] = p->adjvex;
visit(p->adjvex);
vis[p->adjvex] = 1;
}
p = p->next;
}
}
}
|
图不连通的时候（一个顶点不足以访问全部的顶点）
1
2
3
4
5
6
7
8
9
10
11
12
|
void dfs(AGraph *g,int v,int vis[]){
for(int i = 0;i < g->vexNum;i++)
if(vis[i] == 0)
DFS(g,v,vis);
}
void bfs(AGraph *g,int v,int vis[]){
for(int i = 0; i < n;i++)
if(vis[i] == 0)
BFS(g,v,vis);
}
|
最小生成树
如果连通图是个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。
最小生成树：带权连通图中代价最小的生成树称为最小生成树。
prim（普里姆算法）：归并点
思想：
1.从起点顶点开始，将与起始顶点相邻的边作为候选边；
2.从候选边中挑选一条最短且不与生成树构成回路的路径输出，并将这一条边（包含顶点）加入生成树中，将与这条边相邻的边加入候选边中；
3.重复执 2 操作，直到所有节点都被访问。
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
| void Prim(MGraph *g,int v){
int sum = 0;
int vis[Maxn];
int lowcost[Maxn];
for(int i = 1 ; i < g->vexNum;i++){
lowcost[i] = g->edges[v][i];
vis[i] = 0;
}
vis[v] = 1;
int j, k;
for(int i = 1; i < g->vexNum;i++){
int minnest = Maxn;
for(j = 1; j < g->vexNum;j++){
if(lowcost[j] < minnest && vis[j] == 0){
minnest = lowcost[j];
k = j;
}
}
}
sum += minnest;
vis[k] = 1;
for(j = 1;j < g->vexNum;j++){
if(vis[j] == 0 && g->edges[k][j] < lowcost[j])
lowcost[j] = g->edges[k][j];
}
}
|
克鲁斯卡尔：归并边
思想：
1.将图中的边按照权值从小到大进行排序；
2.从最小边开始扫描，如果加入生成树中不构成回路，则加入生成树；并查集判断是否构成回路（判断边的两个顶点的根节点是否相同）
3.重复 2 操作，直到所有边都被扫描为止。
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
| struct Road{
int a, b;
int weight;
boll operator < (Road a)const{
return weight < a.weight;
}
};
int v[Maxn];
int getRoot(int a){
while(a != v[a])
a = v[a];
retur a;
}
Road road[Maxn];
void Kruskal(MGraph *g,int v){
int sum = 0;
int e = g->arcNum;
int v = g->vexNum;
sort(road + 1,road + 1 + e , cmp);
for(int i = 1; i <= v; i++)
v[i] = i;
for(int i = 1; i <= e; ++i){
int a = getRoot(road[i].a);
int b = getRoot(road[i].b);
if(a != b){
sum += road[i].weight;
if(a < b)
v[a] = b;
else
v[b] = a;
}
}
}
|
最短路径
迪杰斯特拉 ：
最短路径 单源点最短路径 和prim对比记忆
思想：
1.将起始结点v并入空集S中，将其余结点并入空集T中；
2.从T中选出一条到v顶点中的最短路径，加入集合S中，并更新v到T中其余各顶点的最短路径；（不能重复访问）prim
3.重复 2 操作直到所有顶点都并入S中为止。
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
| void Dijkstra(MGraph *g, int v){
int vis[Maxn];
int path[Maxn];
int dist[Maxn];
for(int i = 0;i < g->vexNum; i++){
dist[i] = g->edges[v][i];
vis[i] = 0;
}
vis[v] = 1;
int k;
for(int i = 1;i < g->vexNum;i++){
int minn = Maxn;
for(int j = 0;j < g->vexNum;j++)
if(dist[j] < minn && vis == 0){
minn = dist[j];
k = j;
}
}
vis[k] = 1;
for(int j = 0;j < g->vexNum;j++)
if(vis[j] == 0 && dist[k] + edges[k][j] < dist[j]){
dist[j] = dist[k] + edges[k][j];
}
}
void Print(int path[], int j){
int stc[Maxn];
int top = -1;
while(path[j] != -1){
stc[++top] = j;
j = path[j];
}
stc[++top] = j;
while(top != -1)
cout << stc[--top] << '';
cout << endl;
}
|
弗洛伊德：任意一对顶点的最短路径
思想：
1.首先开一个二维数组存放图中各边的权值，再开一个二维数组存放各路径;
2.接着开个三重循环，外层从1到n表示每次比较中间的结点，中间一层表示行的枚举，最内层表示列的枚举；
3.利用三重循环，每一次比较边的两端点直接路径与加入中间结点的路径长短，如小于则用加入中间结点的路径值来替代两端点的直接路径值（取它们最小值），并把中间结点接入路径数组中；
4.完成三个循环结束。
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 Floyd(MGraph *g,int v,int A[][],int path[][]){
for(int i = 0;i < g->vexNum;i++)
for(int j = 0;j < g->vexNum;j++){
A[i][j] = g->edges[i][j];
path[i][j] = -1;
}
for(int k = 0;k < g->vexNum;k++)
for(int i =0;i < g->vex)
for(int j = 0;j < g->vexNum;j++)
if(A[i][j] > A[i][k] + A[k][j]){
A[i][j] = A[i][k] + A[k][j];
path[i][j] = k;
}
}
void Print_f(int u,int v,int path[][],int A[][]){
if(A[u][v] == Maxn)
return;
else if(path[u][v] == -1)
cout << u <<' '<< v;
else{
int mid = path[u][v];
Print_f(u, mid, path, A);
Print_f(mid, v, path, A);
}
}
|
拓扑排序：判断是否为有向无环图（删除的结点是否为n个）
思想：从入度为0的结点开始删除（每次删除结点和相关的边）
1.首先将图中入度为0的结点入栈，栈初始为空；
2.当栈非空时栈首元素出栈，访问并且将与元素相邻顶点的入度减1；（去掉相关的边）
3.当某个顶点在去掉相关边后入度为0，则入栈；
4.重复执行 2 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
struct ArcNode{
int adjvex;
ArcNode *next;
};
struct VNode{
int data;
int cnt;
ArcNode *firstarc;
};
struct AGraph{
VNode adjlist[Maxn];
int vexNum,arcNum;
};
int Puop(AGraph *G){
int n = 0;
int stc[Maxn],top = -1;
for(int i = 0;i < G->vexNum;i++)
if(G->adjlist[i].cnt == 0)
stc[++top] = i;
ArcNode *p;
while(top != -1){
int k = stc[top--];
visit(k);
n++;
p = G->adjlist[k].firstarc;
while(p != NULL){
int j = p->adjvex;
--G->adjlist[j].cnt;
if(G->adjlist[j].cnt == 0)
stc[++top] = j;
p = p->next;
}
}
if(n == G->vexNum)
return 1;
else
return 0;
}
|
求 AOE 中关键路径和关键活动（给你图要会求关键路径）
微信
支付宝
