图论算法汇总与差别详解 _图论算法

前言
因为图论里算法比较复杂和乱，所以整理了一下，将其放在同一个程序里，比较执行。也是新的整理和理解。
white主调
struct E {int a, b, w;bool operator<(const E& temp) {return this->w < temp.w;//重点是有序的}}edge[N*2];int find(int a) {if (p[a] != a)p[a] = find(p[a]);return p[a];}void add(int a, int b, int c) {e[idx] = b,w[idx]=c;ne[idx] = h[a];h[a] = idx++;}
if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];//更新距离cpa[j] = cpa[t] + 1;//如果大于等于n,则出现自己到自己的负环情况，则终止循环，表示存在负环if (cpa[j] >= n) return true;if (!st[j]) { //如果不在队列中q.push(j);st[j] = true;}}
代码集成实现
#includeusing namespace std;const int N = 1e4 + 10;int dist[N], st[N], degree[N];int h[N], ne[N], e[N], w[N],idx;int n, m;//默认记点从0开始int g[N][N],res;void add(int a, int b, int c) {e[idx] = b,w[idx]=c;ne[idx] = h[a];h[a] = idx++;}void addtopsort(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;}//在topsort函数里int q[N];int hh = 0, tt = -1;//模仿q和queue，存放好度数数据为0的就是已经遍历结束后入队列void topsort() {for (int i = 0; i < n; i++) {if (degree[i] == 0) q[++tt] = i;}while (hh <= tt) {int a = q[hh++];for (int i = h[a]; i != -1; i = ne[i]) {int b = e[i];degree[b]--;if (degree[b] == 0)q[++tt] = b;}}//顺便记住了拓扑序列if (tt == n - 1)for (int i = 0; i < n; i++)cout << q[i] << " ";else cout << -1;//不是这一个线路里的}//如果变成了大量访问，那么就相当于是add构建一个基本图，然后query依次减，看看能不能依靠入度走完全程/*for(int i=0;i>query[j];d[j]=degree[j];}if(topsort())demon[i]=1;else demon[i]=0;}for(int i=0;i PII;int heapdijkstra() {//堆优化之后迪杰特斯拉算法memset(dist, 0x3f, sizeof(dist));dist[1] = 0;priority_queue, greater>heap;//大跟堆first是值，second是序号//while(heap.size())都可以，反正还是要加入的heap.push({ 0,1 });while (!heap.empty()) {auto t = heap.top();heap.pop();int u = t.second, distance = t.first;if (st[u])continue;st[u] = true;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (dist[j] > dist[u] + w[i]) {dist[j] = dist[u] + w[i];heap.push({ dist[j],j });/*不论是dijkstra里的什么理解是第 i的dist 是从1到u的距离加上外面的点i的距离变成新的dist i；最小值，可以使用min化dist[j]=min(dist[j],dist[u]+w[i])或者如果堆优化就要加入队列里新的dist路径，dist[j],j结合pII的数据结构设定，左侧距离，右侧点*/}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];}void prim()//考察的是点,同时在数据操作中也有变换，常面临的是邻接矩阵{memset(dist, 0x3f3f, sizeof(dist));dist[0] = 0;for (int i = 0; i < n; i++) {int t = -1;for (int j = 0; j < n; j++) {if (!st[j] && (t == -1 || dist[j] < dist[t]))t = j;}st[t] = 1;res += dist[t];for (int i = 0; i < n; i++) {if (dist[i] > g[t][i] && !st[i])dist[i] = g[t][i];}}cout << res;}//krustra利用结构体int p[N];//并查集寻根问祖,也从侧面说明了针对的是边排序后加入最小判断=是否闭环struct E {int a, b, w;bool operator<(const E& temp) {return this->w < temp.w;//重点是有序的}}edge[N*2];int find(int a) {if (p[a] != a)p[a] = find(p[a]);return p[a];}int cnt = 0;void krustra() {for (int i = 0; i <= m; i++) {int pa = find(edge[i].a);int pb = find(edge[i].b);if (pa != pb) {res += edge[i].w;p[pa] = pb;cnt++;}}}bool isperfectpic(int cnt) {if (cnt < n - 1) {//如果保留的边小于点数-1，则不能连通cout << "impossible";}}int backup[N];//为了数组的稳定性void bellman_ford() {memset(dist, 0x3f, sizeof(dist));dist[1] = 0;for (int i = 0; i < n; i++) {memcpy(backup, dist, sizeof dist);int flag = 0;for (int j = 0; j < m; j++) {int a = e[j], b = ne[a];//eg :边从a-bdist[b] = min(dist[b], backup[a] + w[a]);}/*Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n - 1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。找每一步的最短距离*/}}//松弛的祖师爷，矩阵列表g来确定dist.可以理解成dpvoid floyd() {for (int k = 1; k <= n; k++) {for (int i = 1; i < n; i++) {for (int j = 1; j <= n; j++) {g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}}}}//可以用q数组存队列，也可以直接queue q;void spfa() {q[++tt] = 1;dist[1] = 0;st[1] = 1;//找起点，或者默认1也行while (hh <= tt) {int a = q[hh++];st[a] = false;for (int i = h[a]; i != -1; i = ne[i]) {int j = e[i];if (dist[j] > dist[a] + w[i]) {dist[j] = dist[a] + w[i];if (!st[j]) {q[++tt] = j;st[j] = 1;//spfa反复入队}}}}}int cpa[N];//计算环int spfaque() {queue q;for (int i = 1; i <= n; i++) {st[i] = true;q.push(i);}while (q.size()) {int t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];//更新距离cpa[j] = cpa[t] + 1;//如果大于等于n,则出现自己到自己的负环情况，则终止循环，表示存在负环if (cpa[j] >= n) return true;if (!st[j]) { //如果不在队列中q.push(j);st[j] = true;}}}}}int main(){scanf("%d %d", &n, &m);memset(st, 0, sizeof(st));memset(h, -1, sizeof(h));memset(g, 0x3f, sizeof(g));for (int i = 0; i < m; i++) {int a, b, c;scanf("%d %d %d", &a, &b, &c);add(a, b, c);addtopsort(a, b);g[a][b] = c;degree[b]++;edge[i] = { a,b,c };//结构的加入}sort(edge + 1, edge + m + 1);krustra(); isperfectpic(cnt);//同样可以运用于topsort和最小生成单支树，也可以求restopsort();//是否是完整图prim();//求最小生成树，res，返回前序结点，周游的路径int u;//以某点为起点的遍历，更有应用实践性dijkstra(u);heapdijkstra();//多快好省bellman_ford();floyd();spfa();//spfaque同理，可以用queue看着更舒服//解决负权值的问题，性价比比较高，价值等同于堆优化的dij//可以理解成松弛的用min ，其他的都比较一下好用于数据的其他操作}
下面讲一道融合上面所以算法思路和代码的应用题，也许有点烧脑，但也是将知识点融合的好题
判断有无向图，有无正负权值，连通图，find并查集
航路与道路
农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 T 个城镇，编号为 1～T 。

文章插图
这些城镇之间通过 R 条道路 (编号为 1 到 R) 和 P 条航线 (编号为 1 到 P) 连接。
每条道路 i 或者航线 i 连接城镇 Ai 到 Bi，花费为 Ci 。
对于道路， 0≤Ci≤10,000;然而航线的花费很神奇，花费 Ci 可能是负数(?10,000≤Ci≤10,000) 。
道路是双向的，可以从 Ai 到 Bi，也可以从 Bi 到 Ai ，花费都是 Ci 。
然而航线与之不同，只可以从 Ai 到 Bi 。
事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 Ai 到 Bi，那么保证不可能通过一些道路和航线从 Bi 回到 Ai 。
由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。
他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案。
下图重点解释，如何将道路和航路的两种复合图连通在一起，并进spfa（）算法可以算的同时
也可以用通过并查集实现的方法，第二种方法更好理解，也是主流思想，不会拘束与数据问题

#includeusing namespace std;const int N=1e6+10;int dist[N];typedef pair PII;bool st[N];int n,mr,mh,s,e[N],h[N],ne[N],idx,w[N];int id[N],deg[N],bcnt;int q[N],hh,tt=-1;vector block[N];void add(int a,int b,int c){e[idx]=b,w[idx]=c;ne[idx]=h[a];h[a]=idx++;}void dijkstra(int block_id){priority_queue,greater>heap;for(int u:block[block_id]){heap.push({dist[u],u});}while(heap.size()){PII t=heap.top();heap.pop();int u=t.second;if(st[u])continue;st[u]=true;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[u]+w[i]){dist[j]=dist[u]+w[i];if(id[j]==block_id)heap.push({dist[j],j});}if(id[j]!=block_id&&--deg[id[j]]==0)q[++tt]=id[j];}}}void dfs(int u){lock[bcnt].push_back(u);id[u]=bcnt;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!id[j])dfs(j);}//找链接}void topsort(){memset(dist,0x3f,sizeof(dist));dist[s]=0;for(int i=1;i<=bcnt;i++){if(!deg[i])q[++tt]=i;}while(hh<=tt){int t=q[hh++];dijkstra(t);}}int main(){memset(h,-1,sizeof(h));scanf("%d %d %d %d",&n,&mr,&mh,&s);for(int i=0;i 0x3f3f3f3f / 2) puts("NO PATH");else printf("%d\n", dist[i]);}return 0;}

AOE图与AOV图
工序代号是弧线，事件是点集合
事件是v点
活动是弧线
关键活动是按照时间余量作差后相等就是关键事件

#includeusing namespace std;#define MAX 25typedef char Vertype;typedef int Edgetype;typedef int Status;//构造图的有向图的邻接表结构体typedef struct EdgeNode//边表结点存放每个顶点的邻接点{int adjvex;//边表下标Edgetype weight;//边表权重若边不存在时即无NULLstruct EdgeNode* next;//指向下一个邻接点}EdgeNode;typedef struct VerNode//顶点表存放顶点{int in;Vertype data;//顶点元素EdgeNode* firstedge;}VerNode, AdjList[MAX];//邻接表的 顶点元素 和指向邻点的指针typedef struct{AdjList adjList;//邻接表int numVer, numEdge;//顶点数目和边的数目}GraphAdjList;//构造两个栈typedef struct Stack{int data[MAX];//int pop;}SqStack;//生成邻接表Status CreatGraph(GraphAdjList& G){int i, j, k;Edgetype w;EdgeNode* e;cout << "Enter the number of vertices :" << endl;cin >> G.numVer;cout << "Enter the number of Edges :" << endl;cin >> G.numEdge;cout << "Input vertex content :" << endl;for (i = 0; i < G.numVer; i++){cin >> G.adjList[i].data;//输入顶点元素G.adjList[i].in = 0;G.adjList[i].firstedge = NULL;//初始化邻边表为NULL；}for (k = 0; k < G.numEdge; k++){cout << "Enter the vertex number of the edge (Vi->Vj)" << endl;cin >> i;cin >> j;cout << "Enter the weight of edge" << i << "-" << j << endl;cin >> w;e = new EdgeNode;//将两个顶点相结即可 。e->adjvex = j;// 邻接序号为je->next = G.adjList[i].firstedge;//i的第一个邻接指针 为e的指针e->weight = w;G.adjList[i].firstedge = e;G.adjList[j].in++;//有向图则只有生成一次即可/*e = new EdgeNode;e->adjvex = i;//无向图 重复一遍e->next = G.adjList[j].firstedge;G.adjList[j].firstedge = e;e->weight = w;*/}return 0;}SqStack* etv, * stack2;SqStack* ltv;/*事件最晚发生时间*/int top2;//拓扑排序Status TOpologicalSort(GraphAdjList& G){EdgeNode* e;//SqStack Q;int i, j, k, gettop;int top = 0;int count = 0;SqStack* Q;Q = new SqStack;for (i = 0; i < G.numVer; i++){if (G.adjList[i].in == 0)Q->data[++top] = i;//存放入度为0的顶点}top2 = 0;/*初始化 事件最早发生的时间为0*///SqStack *etv,*stack2;etv = new SqStack;for (i = 0; i < G.numVer; i++){etv->data[i] = 0;}stack2 = new SqStack;while (top != 0){gettop = Q->data[top--];//弹出入度为0的下标stack2->data[++top2] = gettop;//按照拓扑顺序保存弹出顶点下标count++;//统计拓扑网顶点数目//后面输出其边顶点//并删除边，使得边顶点入度-1for (e = G.adjList[gettop].firstedge; e; e = e->next){j = e->adjvex;if (!(--G.adjList[j].in))//如果入度为1时自减后进入循环如果入度不为1，自减后 相当于边的数目减1{Q->data[++top] = j;//保存后续入度为0的顶点}/**/if ((etv->data[gettop] + e->weight) > etv->data[j]){etv->data[j] = etv->data[gettop] + e->weight;//保存权值etv初始化都为0，}}}if (count < G.numVer){cout << "不是一个网图" << endl;return 1;}else{cout << "是一个网图" << endl;return 0;}//return 0;}Status CriticalPath(GraphAdjList& G){EdgeNode* e;int i, j, k, gettop;int ete, lte;/*活动最早发生时间ele活动最迟发生时间lte*/ltv = new SqStack;/*初始化ltv*/for (i = 0; i < G.numVer; i++){ltv->data[i] = etv->data[G.numVer - 1];}while (top2 != 0){gettop = stack2->data[top2--];for (e = G.adjList[gettop].firstedge; e; e = e->next){k = e->adjvex;if (ltv->data[k] - e->weight < ltv->data[gettop]){ltv->data[gettop] = ltv->data[k] - e->weight;}}}for (j = 0; j < G.numVer; j++){for (e = G.adjList[j].firstedge; e; e = e->next){k = e->adjvex;ete = etv->data[j];lte = ltv->data[k] - e->weight;if (ete == lte){cout << G.adjList[j].data << G.adjList[k].data << e->weight << endl;}}}return 0;}int main(){GraphAdjList G;CreatGraph(G);TOpologicalSort(G);CriticalPath(G);system("pause");return 0;}

【图论算法汇总与差别详解】