图论相关知识（DFS、BFS、拓扑排序、最小代价生成树、最短路径）
- 2020 年 7 月 22 日
- 筆記
图的存储
假设是n点m边的图：
邻接矩阵：很简单，但是遍历图的时间复杂度和空间复杂度都为n^2，不适合数据量大的情况
邻接表：略微复杂一丢丢，空间复杂度n+m，遍历图的时间复杂度为m，适用情况更广
前向星：静态链表，即用数组实现邻接表的功能。对于每个顶点，前向星存储的是该顶点的邻接边而非邻接点，head[maxn]存储的是顶点信息，edge[maxm]存储的是顶点对应的边的信息
struct Edge { int to;///某个顶点u的邻接点 int next;///顶点u的下一条邻接边的编号 int val;///该邻接边的权值 Edge(){} Edge(int _to,int _next,int _val){ to=_to;next=_next;val=_val; } edge[maxm*2]; //无向图，建图时边的个数为两倍 int head[maxn],tot=0; ///head用来表示以i为起点的第一条边存储的位置，tot读入边的计数器 void add_edge(int from,int to,int valt)///在图中添加边，O(M) { edge[tot]=Edge(to,head[from],valt); head[from]=tot++; } void read() //遍历所有边，O(N*M) { for(int i=0; i<=n; i++) for(int j=head[i]; j！=-1; j=edge[j].next) }
前向星
DFS/BFS
DFS（深度优先搜索）：递归
BFS（广度优先搜索）：队列（访问顶点，顶点出队，搜索相邻顶点入队；只要队列不空，则重复如下操作：队首元素出队，从队首元素搜索相邻下一步）
记忆化搜索：需要提前计算打表，或者将已经访问的元素保存
适用问题：最优解、计数问题、图论等
- 最优解问题：DFS通常是搜索所有可能的结果来求最优解；BFS本身一层层向下搜索的特点，适合求解最优问题；
- 计数问题：DFS彻底完成一个分支之后再去进行下一个分支，并且搜索所有可能结果，所以更适合计数问题；BFS因为队列里同时有多个未完成的分支、所以在解计数问题中并不常见；
- 图论：DFS、BFS是图论中遍历图的方式，在最短路、迷宫类游戏中很常见。（BFS求最短路径，DFS求所有完整路径）
拓扑序列
适用问题：
- 在某一个有向图graph中，假设每一条有向边(u,v)代表节点u必须排在节点v的前面，那么按照这样的规则，将所有的节点进行排序，最终得出的序列就称为拓扑序列。只要能将事物抽象成有向图，并要求按规则排序，那么就可以考虑拓扑排序，比如选修课程的安排、按胜负排名次等。
- 拓扑排序只适用于有向无环图，所以使用拓扑排序的第一步就是先将问题抽象成有向图，进行图的初始化、建立等工作，然后运行拓扑排序算法即可。
- 顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！
- 简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
算法步骤：
- 新建node类，包含节点数值和它的指向(这里直接用list集合替代链表了)
- 初始化，添加每个节点指向的时候同时被指的节点入度+1！(A—>C)那么C的入度+1；
- 扫描一遍所有node。将所有入度为0的点加入一个栈(队列)。
- 当栈(队列)不空的时候，抛出其中任意一个node(栈就是尾，队就是头，顺序无所谓，上面分析了只要同时入度为零可以随便选择顺序)。将node输出，并且node指向的所有元素入度减一。如果某个点的入度被减为0，那么就将它加入栈(队列)。
- 重复上述操作，直到栈为空。
const int maxnum=505; bool graph[maxnum][maxnum];///邻接矩阵，保存图 int indegree[maxnum];///每个点的入度 void top_sort(int n)///对n个数进行拓扑排序 { vector<int> ans;///保存拓扑序 priority_queue<int, vector<int>, greater<int> > myque;///维护节点入度 for(int j=1;j<=n;j++)///找出入度为0的点，放入最小优先队列，小的值先弹出 { if(indegree[j]==0) { myque.push(j); } } for(int i=1;i<=n;i++) { int toptmp=myque.top(); ans.push_back(toptmp);///把已找出的数放入数组 myque.pop(); for(int j=1;j<=n;j++) { if(graph[toptmp][j]) { indegree[j]--;///删除第一个数后，它指向的点的入度-1 if(indegree[j]==0)///如果入度为0，加入队列 myque.push(j); } } } ///最后输出即可 for(int i=0;i<ans.size()-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[ans.size()-1]); } int main() { int n=0,m=0; while(scanf("%d %d",&n,&m)!=EOF) { memset(indegree, 0, sizeof(indegree)); memset(graph, false, sizeof(graph)); for (int i = 0; i < m; i++) { int p1, p2; scanf("%d %d",&p1, &p2); if (!graph[p1][p2]) indegree[p2]++; ///统计p2的入度 graph[p1][p2] = true; } top_sort(n); } return 0; }
拓扑序列
最小代价生成树
一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的n-1边，同时这些边的权值和最小。最小生成树是权值之和最小的极小生成树。（假设N点M边）
Prime算法：邻接矩阵实现，时间复杂度O（N^2），对点贪心，适合稠密图
- 输入：一个加权连通图，其中顶点集合为V，边集合为E；
- 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
- 重复下列操作，直到Vnew = V：
- 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- 将v加入集合Vnew中，将<u, v>边加入集合Enew中；
- 输出：使用集合Vnew和Enew来描述所得到的最小生成树。
Kruskal算法：邻接表实现，复杂度O(E*lnE)，对边贪心，适用于稀疏图.
- 记Graph中有v个顶点，e个边
- 新建图Graph_new，Graph_new中拥有原图中相同的e个顶点，但没有边
- 将原图Graph中所有e个边按权值从小到大排序
- 循环：从权值最小的边开始遍历每条边，直至图Graph中所有的节点都在同一个连通分量中（if 这条边连接的两个节点于图Graph_new中不在同一个连通分量中，则添加这条边到图Graph_new中）
最短路径
单源最短路径——Dijkstra：
- 单源最短路问题，可以得到一点到其他各点之间的最短路
- 边的权值不能为负
- 使用邻接矩阵，算法的运行时间是 O(N^2)。使用邻接表，时间复杂度O(MlogN)
const int inf=0x3f3f3f3f; int g[605][605],low[605];///g是邻接矩阵,low是当前顶点到源点的最短距离 bool vis[605];///该点是否被访问 int main() { int m,m,i,j,k; while(scanf("%d%d",&n,&m)!=EOF) { memset(g,inf,sizeof(g)); memset(low,inf,sizeof(low)); memset(vis,inf,sizeof(vis)); for(i=0;i<m;i++)///输入图 { int a,b,c; scanf("%d%d%d",&a,&b,&c); g[a][b]=c;///单向图 } for(i=1;i<n;i++)///初始化此时low数组 low[i]=cost[1][i]; vis[1]=true; for(i=2;i<=n;i++) { int minn=inf; for(j=1;j<=n;j++)/// { if(!vis[j]&&low[j]<minn) { minn=low[j]; k=j; } } vis[k]=true; for(j=1;j<=n;j++)///更新最短距离 { if(!vis[j]&&low[k]+g[k][j]<low[j]) { low[j]=low[k]+g[k][j]; } } } if(low[n]==inf) printf("-1\n"); else printf("%d\n",low[n]); return 0; }
Dijkstra单源最短路径
全源最短路径——Floyed：
- 多源最短路问题，可以得到任意两点之间的最短路；查找无向图中最小环
- 边的权值不能为负值
- 使用邻接矩阵，时间复杂度是O(N^3)。不适用于大量数据。
int n,g[maxn][maxn];///g[i][j]表示从i到j的距离，inf表示i，j之间不直接连通 int dist[maxn][maxn];///dist[i][j]表示i到j的最短距离 int floyed() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=g[i][j]; int min_circle=INF; for(int k=1;k<=n;k++)///枚举k { ///先判断环，后更新，保证判断环时的dist[i][j]不经过 k for(int i=1;i<k;i++) { for(int j=i+1;j<k;j++) { if(dist[i][j]!=INF&&g[i][k]!=INF&&g[j][k]!=INF)///环至少要有3个结点 min_circle=min(min_circle,dist[i][j]+g[i][k]+g[j][k]); ///i-j不经过k的最短路 + 边i-k + 边j-k } } ///以下和求全源最短路一致，更新以k为中介点的最短路 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(dist[i][k]!=INF&&dist[k][j]!=INF) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } } } return min_circle; }
Floyed求无向图的最小环
