首页 > 代码库 > 图论常用算法总结
图论常用算法总结
一、图的可行遍历
1）欧拉图
条件：1、图连通；2、奇度点数为0或2；
算法（一次dfs）
时间复杂度O（E），空间复杂度O（E）
1 //前向星,vis[]标记走过的边,cnt初始为1,i的反向边为i^1 2 void addedge (int u, int v) { 3 edge[++cnt].v = v,edge[cnt].ne = head[u]; 4 head[u] = cnt; 5 } 6 void EulerianP (int x) { 7 for (int i = head[x]; i != 0; i = edge[i].ne) { 8 if (!vis[i]) { 9 vis[i] = vis[i^1]=1;10 EulerianP (edge[i].v);11 }12 }13 //输出顺序即为路径顺序14 printf ("%d\n", x);15 }
2）哈密顿图
哈密顿图的判断是一个NP问题。
当n个点的图当任意不同两点的度数和大于n时，一定存在哈密顿回路。
算法思路：
1、从任意两个相邻的节点S，T开始，拓展出一条尽量长的链，令两端节点为S，T；
2、 若S，T相邻，则出现回路，-》4
3、若没有回路则构造，链中找到节点相邻节点u，v，u与T相连，v与S相连，将原路径变为S->u->T->v,即出现回路；
4、如果回路中有n个点，找到了哈密顿路，否则找到回路中与外一点想连的点，断开。又得到一条链，重复步骤1.
时间复杂度O（n^2）,空间复杂度（n^2）
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 #define pb push_back 8 #define sz(a) (int)(a).size() 9 10 const int INF = 500;11 bool edge[INF][INF];12 typedef vector<int> vi;13 vi ans;14 //求哈密顿回路O(n^2)15 void Hamilton (vi& ans, bool edge[INF][INF], int n) {16 int s = 1, tol = 2, t, i, j;17 bool vis[INF] = {0};18 for (i = 1; i <= n; i++) if (edge[s][i]) break;19 t = i;20 vis[s] = vis[t] = 1;21 ans.pb (s); ans.pb (t);22 while (1) {23 //头尾拓展24 while (1) {25 for (i = 1; i <= n; i++) 26 if (edge[t][i] && !vis[i]) {27 vis[i] = 1; t = i;28 ans.pb (i);29 break;30 }31 if (i > n) break;32 }33 reverse (ans.begin(), ans.end() );34 swap (s, t);35 while (1) {36 for (i = 1; i <= n; i++) 37 if (edge[t][i] && !vis[i]) {38 vis[i] = 1; t = i;39 ans.pb (i);40 break;41 }42 if (i > n) break;43 }44 //如果S和T不相连45 if (!edge[s][t]) {46 for (i = 1; i < sz (ans) - 2; i++)47 if (edge[ans[i]][t] && edge[ans[i + 1]][s]) break;48 reverse (ans.begin() + i + 1, ans.end() );49 t = * (ans.end() - 1);50 }51 tol = sz (ans);52 if (tol == n) return;53 //如果还有点未加入ans54 for (j = 1; j <= n; j++) {55 if (vis[j]) continue;56 //找到与这个点相连的点57 for (i = 1; i < tol - 1; i++) if (edge[ans[i]][j]) break;58 if (edge[ans[i]][j]) break;59 }60 s = ans[i - 1], t = j;61 reverse (ans.begin(), ans.begin() + i );62 reverse (ans.begin() + i, ans.end() );63 ans.pb (j), vis[j] = 1;64 }65 }
算法特点：一般看似NP的哈密顿路的判断问题可以通过变化成为欧拉路问题，也是解题的关键。
二、图的生成树
1）最小生成树
prim（堆优化）时间复杂度O（（n+m）logN）
kruskal 时间复杂度O（mlogm+m）
2）次小生成树
思路：从生成的最小生成树中加入一条后，去掉环中除新加边外最大的边
使用prim，思路更加直观：每加入一个点，更新当前集合中任意两点间的最长边的长度。
生成最小生成树后，加入从未使用的过的最短边（u，v），u，v间的最长边与（u，v）的差就是次小生成树与最小生成树的差
//图的次小生成树：//从生成的最小生成树中加入一条后，去掉环中除新加边外最大的边//1.prim实现时间复杂度O（N*N+M*logM）#include <iostream>#include <cstring>using namespace std;const int INF = 111;//记录两点间路径上的最长边长度int maxl[INF][INF];//前向星存边struct node { int u, v, len, ne, id;} edge[INF*INF];//vise标记选择了哪些边//dis记录从当前选择节点中到其他节点的最短距离以及边的编号.int cnt, head[INF], dis[INF][2], vise[INF*INF];void addedge (int u, int v, int d) { edge[++cnt].v = v, edge[cnt].u = u; edge[cnt].len = d, edge[cnt].ne = head[u]; edge[cnt].id = head[u] = cnt;}void update (int x) { for (int i = head[x]; i != 0; i = edge[i].ne) { int v = edge[i].v, c = edge[i].len; if (dis[v][0] > c) dis[v][0] = c, dis[v][1] = i; }}int second_MST_prim (int n) { bool vis[INF] = {0}; bool vise[INF * INF] = {0}; memset (dis, 0x3f, sizeof dis); memset (maxl, 0, sizeof maxl); vis[1] = 1, update (1); int ans = 0, tol = 1, j, now = 1; while (tol < n) { int minl = 0x3f3f3f3f; for (int i = 1; i <= n; i++) if (!vis[i] && minl > dis[i][0]) minl = dis[i][0], j = i; for (int k = 1; k <= n; k++) maxl[k][j] = maxl[j][k] = max (maxl[now][k], minl); maxl[j][j] = 0, update (j), vis[j] = 1; vise[dis[j][1]] = vise[dis[j][1] ^ 1] = 1; now = j, tol++, ans += minl; } int tem = 0x7fffffff; for (int i = 2; i <= cnt; i++) if (!vise[edge[i].id]) tem = min (tem, edge[i].len - maxl[edge[i].u][edge[i].v]); if (tem != 0) return ans; else return -1;}
3)有向图的最小树形图
朱刘算法
思路：
1、从图G找到以每个点为终点的最小弧。构成子图G’
2、若无有向环和收缩点，算法结束。
3、收缩G’的有向环为，改变到环中点的边权。
4、展开收缩点。（若只求最小权可不做）
确定根的情况
#include <iostream>#include <utility>#include <cstdio>#include <cstring>#include <cmath>#define sqr(a) (a)*(a)using namespace std;const int INF = 109;const int Max=(1<<30);int n, m, x, y;typedef pair<int , int > ii;struct node { int u, v; double c;} E[INF*INF];ii f[INF];//最小树形图，朱刘算法，确定根double Directed_MST (int root, int n, int m, node E[INF]) { int Din[INF], ret = 0; //记录最短入边 int pre[INF], Np[INF], vis[INF];//记录最小边的出顶点 for (int i = 1; i <= n; i++) Np[i] = i; while (1) { int cnt = 0;//统计有入边的点 for(int i=1;i<=n;i++) Din[i]=-1; //得到每个点的最小入边和出顶点 for (int i = 1; i <= m; i++) { if ( E[i].v == E[i].u || E[i].v==root) continue; if (Din[E[i].v] > E[i].c || (Din[E[i].v]<0 && ++cnt) ) Din[E[i].v] = E[i].c, pre[E[i].v] = E[i].u; } //图不联通,不存在最小树形图 if (cnt < n - 1) return -1; memset (Np, -1, sizeof Np); memset (vis, -1, sizeof vis); Din[root] = 0; //找环 int cntnode = 1; for (int i = 1; i <= n; i++) { ret += Din[i]; int v = i; while (vis[v] != i && Np[v] == -1 && v != root) { vis[v] = i; v = pre[v]; } if (v != root && Np[v] == -1) { for (int u = pre[v]; u != v; u = pre[u]) Np[u] = cntnode; Np[v] = cntnode++; } } if (cntnode == 1) break; //无环 for (int i = 1; i <= n; i++) if (Np[i] == -1) Np[i] = cntnode++; //缩点，改变边长 for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v; E[i].u = Np[u]; E[i].v = Np[v]; if (E[i].u != E[i].v) { E[i].c -= Din[v]; } } n = cntnode-1; root = Np[root]; } return ret;}
不确定根的情况
#include <iostream>#include <utility>#include <cstdio>#include <cstring>#include <cmath>#define ll __int64#define sqr(a) (a)*(a)using namespace std;const int INF = 1009;const int Max = 1 << 30;int n, m, r, tol = 1;struct node { int u, v, c;} E[INF*INF];/* 最小树形图，朱刘算法，适用不确定根 需要记录 tol（图中所有边长和+1,可初始为1） 4个参数分别为（节点数，边数，E边集数组，根地址） 时间复杂度O（VE）*/ll Directed_MST (int n, int m, node E[INF], int &p) { //添加“假根”的出边 for (int i = 1; i <= n; i++) { E[++m].u = n + 1, E[m].v = i, E[m].c = tol; } int pre[INF], Np[INF], vis[INF], root = ++n; //记录最小边的出顶点 ll Din[INF], ret = 0; //记录最短入边 while (1) { int cnt = 0;//统计有入边的点 memset(Din,-1,sizeof Din); //得到每个点的最小入边和出顶点 for (int i = 1; i <= m; i++) { if ( E[i].v == E[i].u || E[i].v == root) continue; if (Din[E[i].v] > E[i].c || (Din[E[i].v]<0 && ++cnt) ) { Din[E[i].v] = E[i].c, pre[E[i].v] = E[i].u; if (E[i].u == root) p = i;//用到了假根的第几个边即真正根的编号 } } if (cnt < n - 1) return -1;//图不联通,不存在最小树形图 memset (Np, -1, sizeof Np); memset (vis, -1, sizeof vis); Din[root] = 0; //找环 int cntnode = 1; for (int i = 1; i <= n; i++) { ret += Din[i]; int v = i; while (vis[v] != i && Np[v] == -1 && v != root) { vis[v] = i; v = pre[v]; } if (v != root && Np[v] == -1) { for (int u = pre[v]; u != v; u = pre[u]) Np[u] = cntnode; Np[v] = cntnode++; } } if (cntnode == 1) break; //无环 for (int i = 1; i <= n; i++) if (Np[i] == -1) Np[i] = cntnode++; //缩点，改变边长 for (int i = 1; i <= m; i++) { int u = E[i].u, v = E[i].v; E[i].u = Np[u], E[i].v = Np[v]; if (E[i].u != E[i].v) E[i].c -= Din[v]; } n = cntnode - 1; root = Np[root]; } return ret;}int main() { while (~scanf ("%d %d", &n, &m) ) { int x, y, z; for (int i = 1; i <= m; i++) { scanf ("%d %d %d", &x, &y, &z); E[i].u = x + 1, E[i].v = y + 1, E[i].c = z; tol += z; //累计所有边长，赋值给“假根” } ll ans = Directed_MST (n , m, E, r); if (ans == -1 || ans >= 2 * tol) puts ("impossible"); else printf ("%I64d %d\n", ans - tol, r - m - 1); putchar (10); } return 0;}
图论常用算法总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。