图论(实践篇)
图的存储
-
邻接矩阵：
int g[i][j]=w;：从i到j有一条边权为w的边 -
邻接表：
-
不带边权：vector<vector
> q vector<vector<int>> q; void my_add(int a,int b) { q[a].push_back(b); } void bianli(int a) { for(auto w:q[a]) { //遍历a可通向的所有边w } } //可通过再增加一个map<int,int> mp[N]; mp[a][b]=c;把边权存进去 -
带边权：h[N],e[N],ne[N],w[N],idx
int h[N],e[N],ne[N],w[N],idx;//memset(h,-1,sizeof h) void my_add(int a,int b,int c) { e[idx]=b; ne[idx]=h[a]; w[idx]=c; h[a]=idx++; }//添加了一条从a到b边权为c的边
-
-
其他
-
结构体存储：Bellman-Ford算法需要利用每条边来迭代；Kruskal算法需要对每条边进行排序
struct Edge { int a,b,w; }g[N]; void add(int m,int a,int b,int w) { for(int i=0;i<m;i++) g[i]={a,b,w}; }
-
图的搜索
-
深度优先搜索DFS：递归
void dfs(int u) { st[u]=true; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(!st[j]) dfs(j); } } -
宽度优先搜索BFS：队列
void bfs(int u) { queue<int> q; while(q.size()) { int t=q.front(); q.pop(); st[t]=true; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(!st[i]) q.push(j); } } }
图的应用
最短路算法
-
单源最短路
-
无负边权
-
朴素Dijkstra算法： O(n2)，适用稠密图
int g[N][N]; //邻接矩阵存储稠密图 int dise[N]; //dist[i]存储从起点到i的最短距离 bool st[N]; //st[i]为真表示：第i个点 int dijkstra(int stat, int end) { //step1:一开始起点外的其他点都不与起点连通，dist[起点]=0，其余为0x3f正无穷 memset(dist, 0x3f, sizeof dist); dist[stat] = 0; //step2:每次更新一个点到起点的距离，故for循环n次，更新n个点到起点的距离 for (int i = 0; i < n; i++) { //step3：每次从未确定最短距的集合里 找到距离最短的点t int t = -1; for (int j = 1; j <= n; j++) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; //step4：用该距离最短的点t 更新其他所有点到起点的最短距 for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]); } return dist[end]; } -
堆优化Dijkstra算法： O(m log n)，适用稀疏图
int h[N],e[N],ne[N],w[N],idx; int dist[N]; bool st[N]; typedef pair<int,int> PII; //小根堆中的每个元素都是一个PII容器，PII.first放距离，PII.second放点编号 priority_queue<PII,vector<PII>,greter<PII>> heap; int heap_dijkstra(int stat,int end) { memset(dist,0x3f,sizeof dist); dist[stat]=0; heap.push({0,stat}); //优化1：不需要for遍历所有点，只需要遍历完heap小根堆 while(heap.size()) { //优化2：通过小根堆直接求出集合外距离最短的点 auto t=heap.top(); heap.pop(); int distance=t.first,ver=t.second; if(st[ver]==true) continue; else st[ver]=true; for(int j=h[ver];j!=-1;j=ne[j]) { int k=e[j]; //优化3：只把更新过最短距的点放进heap中 if(dist[k]>distance+w[i]) { dist[k]=distance+w[i]; heap.push({dist[k],k}); } } } return dist[end]; }
-
-
有负边权
-
Bellman-Ford算法： O(nm)，存在负权回路必须使用该算法
int bellman-ford(int stat,int end) { memset(dist,0x3f,sizeof dist); dist[stat]=0; //step1：一次循环是一次迭代，for循环k次迭代k次 for(int i=0;i<k;i++) { //step2：dist在变化，每次迭代用的是上次的dist备份backup memcpy(backup,dist,sizeof dist); //step3：每次迭代依次枚举所有边来进行更新 for(int j=0;j<m;j++) { int a=g[j].a,b=g[j].b,w=g[j].w; //step:4：bellman-ford迭代方程 dist[b]=min(dist[b],dist[a]+w); } } return dist[end]; } -
SPFA算法： O(m)，最坏O(nm)，也可以解决无负边权问题：优先选择SPFA
int spfa(int stat,int end) { memset(dist,0x3f,sizeof dist); dist[stat]=0; queue<int> q; q.push(stat); st[stat]=true; //优化1：每次只取那些更新了最短距的点来更新其他点的距离 while(q.size()) { int t=q.front(); q.pop(); st[t]=false; //优化2：不需要枚举所有的边，只要枚举当前取出的这个点可到达的边 for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; //优化3：每次只把更新了最短距的点放进队列 if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; //优化4：每次只把未放进过队列里的点放进队列 if(!st[j]) { q.push(j); st[j]=true; } } } } return dist[end]; }
-
-
-
多源最短路
-
Floyd算法： O(n3)，基于动态规划的思想
void floyd() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } //由于floyd算法直接在邻接矩阵上更新最短距，所以在输入邻接矩阵时要先对dist[N]预处理 /* for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) //如果存在自环，就代表dist=0； if(i==j) dist[i][j]=0; //其他情况将dist都定义为0x3f无穷大 else dist[i][j]=0x3f; */
-
最小生成树
-
Prim算法
int prim() { memset(dist, 0x3f, sizeof dist); int res = 0; for (int i = 0; i < n; i++) { int t = -1; for (int j = 1; j <= n; j++) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; if (i && dist[t] == 0x3f) return -1; //如果t不是第一个点，且t到集合的最短距离是正无穷，说明当前的图是不连通的 if (i) res += dist[t]; //先累加，再更新（防止把自环加进来） for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]); //t是新加入到集合里的点，所以更新其余点到集合的最短距 //就等同于min(dist[j]（原本的最短距）,g[t][j](到 新加入集合的点 的距离） st[t] = true; } return res; } -
Kruskal算法
int Kruskal() { int res=0,cnt=0; for(int i=0;i<m;i++) { int a=g[i].a,b=g[i].b,w=g[i].w; if(find(a)!=find(b)) { p[find(a)]=find(b); res+=w; cnt++; } } if(cnt<n-1) return -1; else return res; } //结构体建图，并在结构体中重载小于号，方便sort对结构体中的边权进行排序 /* bool operator <(const Edge& M) const { return w<M.w; } */ //判断两个点是否在同一个集合中，涉及到了并查集的应用
拓扑排序
-
模板：拓扑排序逻辑：只有入度为0的点才会进入下一次的深搜
void topsort() { int q[N],hh=0,tt=-1; //step1：将所有入度为0的点入队 for(int i=1;i<=n;i++) if(!rudu[i]) q[++tt]=i; while(hh<=tt) { //step2：每次取出队头出来深搜 int t=q[hh++]; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; rudu[j]--; //step3：如果入度为0，就将它入队 if(!rudu[j]) q[++tt]=j; } } //step4：如果tt==n-1，说明图中所有点都入队了，说明该图有拓扑排序 if(tt==n-1) { //step5：q[i]数组里存着的就是拓扑序列 for(int i=0;i<n;i++) cout<<q[i]<<" "; } } //注意拓扑排序在建图的时候需要 rudu[b]++; 表示b的入度在增加 -
应用
- 求食物链条数（由所有起点到所有终点的不同路径数）：f[i]：到达i这个点的不同路径数；更新方法：从a搜索到b，则f[b]+=f[a]；初始化：所有入度为0的点的f[i]=1（起点到起点的路径只有一条）；结果：将所有出度为0的点的f[i]相加，即为答案；
- 给出一串任务，每项任务有一些准备工作，问最短多久做完：f[i]：完成第i项任务至少需要的时间，a[i]：单单完成任务i需要的时间；更新方法：f[i]=max(f[i],f[j]+a[i])（为什么是取最大值，因为要保证f[i]前的准备工作全部完成）；初始化：所有入度为0的点的f[i]=a[i]（入度为零说明没有准备工作，则完成自己的时间就是a[i]）；结果：f[i]里的最大值，即为答案