TIP
本文主要是介绍 图-知识点总结 。
# 图
# 定义
G=(V,E)
顶点偶对：（通常不考虑自环，即认为vi, vj不同）
(vi, vj)，无向边、无向图，vi, vj 互为邻接点
<vi, vj>，有向边、有向图，vi 为 vj 的邻接点，vi为弧尾、vj为弧头
带权的图称为网络。
# 基本术语
1、度（TD）、入度（ID）、出度（OD）：各节点度的和等于边数的2倍：2e=(i=1~n)Σ TD(vi)，有向图、无向图均如此。有向图入度和、出度和、边数 三者相等。
=> 无向图度和最大为n(n-1)，故边数最多n(n-1)/2，此时为完全图。
有向图度和最大为2n(n-1)，故边数最多n(n-1)，此时为有向完全图。
=> 稠密图、稀疏图（边或弧的数目是否接近完全图）
2、路径：若顶点序列v1v2...vm有(vi,vi+1)∈E(i=1,2,...m-1)，则为v1到vm的一条路径，有向图类似。
回路或环：起点、终点重合的路径。判断是否有回路可用下面介绍的深度优先遍历或拓扑排序。
简单路径：序列中顶点不重复的路径
简单回路或简单环：除首末顶点外其他顶点均不重复的回路
有根图：有向图若存在一个顶点有到其他所有顶点的路径，则为有根图，此顶点为根
3、子图：G,=(V,, E,)，其中 G, ⊆ G、V, ⊆ V, E, ⊆ E
4、连通：
顶点连通：无向图顶点vi到vj（i≠j）有路径，则vi vj连通；有向图则要求vi到vj及vj到vi（i≠j）都有路径才是连通
***连*通图：无向图任意两个顶点间都是连通的则是连通图。对于一有n个顶点的无向图：若是连通图则边数：[n-1, n(n-1)/2]；若要保证是连通图则边至少需是 ：(n-1)(n-2)/2+1，即此时n-1个顶点构成完全图然后再加一条边。
**强*连*通图：有向图任意两顶点间都是连通的则是强连通图。对于一有n个顶点的有向图，若是强连通图则边数：[n, n(n-1)]；若要保证是连通图则边至少需是：(n-1)(n-2)+2。
连通分量：无向图的极大连通子图。
强连通分量：有向图的极大连通子图。
连通图的连通分量只有一个即为本身，而非连通图的连通分量有多个；强连通图亦然。
5、生成树：连通图包含n个顶点的极小连通子图为其生成树。
连通图才有生成树，其包含n个顶点、n-1条边；生成树可能不唯一，且不一定是最小生成树。
# 图的存储
无向图：邻接矩阵、邻接表、多重邻接表法
有向图：邻接矩阵、邻接表、十字链表法
1、邻接矩阵存储（存所有边，若不带权则不存在的边包括自己到自己表示为0、若带权则表示为∞）
无向图的邻接矩阵是个对称阵，可以用矩阵的压缩存储。
2、邻接表存储（存顶点和邻接的边）：顺序存储与链式存储相结合。（顶点节点、边节点）
无向图邻接表中顶点节点、边节点数分别为n、2e，有向图的则分别为n、e。故无向图邻接表边节点数为偶数，若边节点数为奇数则为有向图。
顶点节点、边节点定义：
1 typedef struct edge//边节点
2 {
3 int adjvex;//该边的终止节点在顶点节点数组中的位置
4 int weight;//边的权重，带权图才需要。
5 struct edge* next;//指向下一边节点
6 }ELink;
7
8 typedef struct ver//顶点节点
9 {
10 int vertex;//顶点节点的信息
11 ELink * link;//指向第一个边节点
12 }VLink;
有向图 第i行非0元素的个数（邻接矩阵存储）或第i个链表边节点的个数（邻接表存储） 等于该节点的出度OD，所有行非0元素个数和或所有链表边节点个数和等于边数e。
无向图 第i行非0元素的个数（邻接矩阵存储）或第i个链表边节点的个数（邻接表存储） 等于该节点的度TD，所有行非0元素个数和或所有链表边节点个数和等于两倍边数2e。
# 图的遍历
指访问每个顶点一次且仅一次。
遍历的过程实质上是通过边或弧寻找邻接点的过程，而采用不同遍历方法时总边节点数是不变的，所以深度优先、广度优先的时间复杂度一样。针对不同存储方法（邻接矩阵、邻接表）的遍历算法类似。
| 邻接矩阵存储 | 邻接表存储 | |
|---|---|---|
| 深度优先（递归） | O(n2) | O(n+e) |
| 广度优先（非递归） | O(n2) | O(n+e) |
1、邻接表存储：O(n+e)
深度优先：
1 #include<stdio.h>
2 #include<malloc.h>
3 typedef struct edge//边节点
4 {
5 int adjvex;//该边的终止节点在顶点节点数组中的位置
6 int weight;//边的权重，带权图才需要。
7 struct edge* next;//指向下一边节点
8 }ELink;
9
10 typedef struct ver//顶点节点
11 {
12 int vertex;//顶点节点的信息
13 ELink * link;//指向第一个边节点
14 }VLink;
15
16
17 void DFS(VLink G[],int n,int visit[],int i)//从下标为i的节点开始遍历，时间复杂度为 O(当前所在连通分量边数)
18 {
19 //VISIT(i);
20 visit[i]=1;
21
22 ELink *p=G[i].link;
23 while(p!=NULL)
24 {
25 i=p->adjvex;
26 if(visit[i]==0)
27 {
28 DFS(G,n,visit,i);
29 }
30 p=p->next;
31 }
32 }
33 void traverse_DFS(VLink G[],int n,int visit[])
34 {
35 int i;
36 for(i=0;i<n;i++)//O(n)
37 {
38 visit[i]=0;
39 }
40 for(i=0;i<n;i++)//O(n+图的边节点数) = O(n+e) （无向图边节点数为2e、有向图为e，故量级为e）
41 {
42 if(visit[i]==0)
43 {
44 DFS(G,n,visit,i);//每执行完一次得到一个连通分量
45 }
46 }
47 }
广度优先：
1 #define M 100
2 void BFS(VLink G[],int n,int visit[],int i)//从下标为i的节点开始遍历，时间复杂度为 O(当前所在连通分量边数)
3 {
4 int queue[M],front=-1,rear=-1;
5
6 //访问后再入队。若出队再访问则会有问题：若当前节点的一个邻接点已经在队里那此时还要不要重复入队，如何判断？
7 //VISIT(i);
8 visit[i]=1;
9 queue[++rear]=i;//ADDQ
10
11 ELink *p;
12 while(front<rear)
13 {
14 i=queue[++front];
15
16 p=G[i].link;
17 while(p!=NULL)
18 {
19 i=p->adjvex;
20 if(visit[i]==0)
21 {
22 //访问后再入队
23 //VISIT(i);
24 visit[i]=1;
25 queue[++rear]=i;//ADDQ
26 }
27 p=p->next;
28 }
29 }
30 }
2、邻接矩阵存储：O(n2)，实现与上类似。
单次DFS或BFS的时间复杂度为O(连通/强连通分量的边数)。
DFS/BFS：单次调用可得到一个连通分量/强连通分量（访问的点+关联的所有边），
DFS：亦可得到该分量的一棵生成树（点连成的边）；可再单次调用DFS时看是否遇到访问过的节点来判断是否有环。
以下为网络（即带权图）相关。
# 最小生成树（MST）
带权图（网络）的生成树中权值和最小的生成树，也叫最小代价生成树。既然是生成树那么就是一个包含n个顶点的连通图，所以能够到达各个顶点，即任意两个顶点间都有路径。最小生成树一般不唯一，但当权值各不相同时唯一。
最小生成树算法（求最大生成树也可以用这两法，只不过每次取权值大的）
1、Prime算法：O(n2)。适合顶点少者。由邻接矩阵求最小生成树。代码如下（与dijkstra的非常相似，只是最后一步的更新信息时不同。可对比参阅）：
1 int primMST(int n,int dist[][DIM],int s,int pre[])//res为MST的权值，pre为每次选进来一个点时与之对应的已选点
2 {
3 int f[n],mdist[n];//标记是否选取点
4
5 int i;
6 for(i=0;i<n;i++)//初始化
7 {
8 f[i]=0;
9 mdist[i]=dist[s][i];
10 pre[i]=s;
11 }
12 f[s]=1;//起点选上
13
14 int tmpMinDist;//inf
15 int tmpMinNode;
16 int j;
17 int res=0;
18 for(i=1;i<n;i++)//添加n-1次节点
19 {
20 tmpMinDist=INF_DIST;
21 for(j=0;j<n;j++)//找出未选节点中mdist最小者
22 {
23 if(!f[j] &&(mdist[j]<tmpMinDist))
24 {
25 tmpMinDist=mdist[j];
26 tmpMinNode=j;
27 }
28 }
29
30 f[tmpMinNode]=1;//将最小者选上并更新到各未选点的距离
31 res+=dist[tmpMinNode][pre[tmpMinNode]];
32 printf("%2d--%2d\n",pre[tmpMinNode],tmpMinNode);//选择的节点对应的边
33 for(j=0;j<n;j++)
34 {
35 if( !f[j] && dist[tmpMinNode][j]<mdist[j] )
36 {
37 mdist[j]=dist[tmpMinNode][j];
38 pre[j]=tmpMinNode;
39 }
40 }
41 }
42 return res;
43 }
2、Kruskal算法：O(elge)，边排序。适合边少者。当e=Ω(n2)时Prime比Kruskal好；当e=o(n2)时相反。
单源最短路径：O(n2)，求得的源点到各节点的最短路径构成了生成树，但一般不是最小生成树。
1、Dijkstra算法：不含负权的单源最短路径。代码：
1 #define DIM 6
2
3 //自身到自身的 距离为0
4 # define INF_DIST 0x0fffffff
5 void dijkstra(int n,int dist[][DIM],int s,int mdist[],int pre[])//参数分别表示 节点数、边权值、起点、要到各点的最短距离、最短距离时该点的前一个点
6 {
7 int f[n];//标记是否选取点
8
9 int i;
10 for(i=0;i<n;i++)//初始化
11 {
12 f[i]=0;
13 mdist[i]=dist[s][i];
14 pre[i]=s;
15 }
16 f[s]=1;//起点选上
17
18 int tmpMinDist;//inf
19 int tmpMinNode;
20 int j;
21 for(i=1;i<n;i++)//添加n-1次节点
22 {
23 tmpMinDist=INF_DIST;
24 for(j=0;j<n;j++)//找出未选节点中mdist最小者
25 {
26 if(!f[j] &&(mdist[j]<tmpMinDist))
27 {
28 tmpMinDist=mdist[j];
29 tmpMinNode=j;
30 }
31 }
32
33 f[tmpMinNode]=1;//将最小者选上并更新到各未选点的距离
34 for(j=0;j<n;j++)
35 {
36 if( !f[j] && dist[tmpMinNode][j]<INF_DIST &&( mdist[tmpMinNode]+dist[tmpMinNode][j] < mdist[j] ) )
37 {
38 mdist[j]=mdist[tmpMinNode]+dist[tmpMinNode][j];
39 pre[j]=tmpMinNode;
40 }
41 }
42 }
43 }
44 void printMinPathForNode(int pre[],int n,int s,int e)//打印从s到e的最短路
45 {
46 if(s!=e)
47 {
48 printMinPathForNode(pre,n,s,pre[e]);
49 }
50 printf("%d ",e+1);
51 }
2、Belman-Ford算法：含负权的单源最短路径；
3、Floyd算法：含负权的任意两点的最短路径。
上述几种算法都属于贪心算法。
# AOV、AOE网络
AOV、AOE网络都是有向图。
1、AOV网络用节点表示活动，一些活动间有先后关系，所以组成了有向图。
判断活动能否顺利开展（即图是否有环）：拓扑排序、深度优先遍历，时间复杂度均为O(n+e)
2、AOE网络：顶点表示事件、边表示活动。某顶点表示的事件发生后从该顶点出发的各有向边表示的活动才能发生；进入某顶点的各有向边表示的活动发生后该顶点表示的事件才能发生。
事件最早发生时间：从前往后，多入取大者（因为不能早于入活动的结束时间）
事件最晚发生时间：从后往前，多出取小者（因为不能晚于出活动的开始时间）
活动最早发生时间：从前往后，前驱事件的最早发生时间
活动最晚发生时间：从后往前，后继事件的最晚发生时间减当前活动的时间
松弛时间：活动最早发生时间与最晚发生时间的差值
关键路径：松弛时间为0的活动构成的路径，其权值和为网络的最大路径长度（Dijkstra等则可以求最短路径，注意区别），亦为工程的最短完成时间。路径可能不唯一，但权值和一样。
# 其他图论相关算法
# 并查集算法
用于解决图的动态连通判断问题，具体可参阅：https://www.cnblogs.com/z-sm/p/12383918.html
# 参考文章
- https://www.cnblogs.com/z-sm/p/6830924.html
