大家好,又见面了,我是全栈君。
SJ图论非常流弊,为了省赛队里知识尽量广,我就直接把图continue,如今回想起来丫的全忘了,从头開始吧。
先写写图的存储,再写写最小生成树和最短路的几个经典算法,月球美容计划就能够结束了。0 0。拖了好久,还有非常多内容要写。- –
这次总结了邻接矩阵,邻接表。十字链表。邻接多重表,边集数组,这5种经常使用的图的储存结构,或许能当模板用吧。
邻接矩阵
#include <stdio.h> #include <stdlib.h> #include <string.h> //邻接矩阵 int G[100][100]; int add1 (int i,int j,int w) { G[i][j] = w; return 0; } int main() { int i,n; //建图 scanf ("%d",&n); for (i = 0;i < n;i++) { int a,b,w; //输入起点、终点、权重 scanf ("%d%d%d",&a,&b,&w); add1 (a,b,w); //无向图加上 add1 (b,a,w); } return 0; }
邻接表
#include <stdio.h> #include <stdlib.h> #include <string.h> //邻接表 struct dot { int d; int w; struct dot *next; }; struct hed { int v; struct dot *next; }head[100]; int add2(int i,int j,int w) { struct dot * p; struct dot * t = new dot; t->d = j; t->w = w; t->next = NULL; if (head[i].next == NULL) { head[i].next = t; return 0; } p = head[i].next; while (p->next != NULL) p = p->next; p->next = t; return 0; } int main() { int i,n; memset (head,0,sizeof (head)); //建图 scanf ("%d",&n); for (i = 0;i < n;i++) { int a,b,w; //输入起点、终点、权重 scanf ("%d%d%d",&a,&b,&w); add2 (a,b,w); //无向图加上 add2 (b,a,w); } return 0; }
十字链表(有向图好用)
#include <stdio.h> #include <stdlib.h> #include <string.h> //十字链表 struct dot { int d; int w; struct dot *next; }; struct hed { int v; struct dot *to; struct dot *next; }head[100]; int add3(int i,int j,int w) { struct dot * p; struct dot * t = new dot; t->d = j; t->w = w; t->next = NULL; //正邻接表构建 if (head[i].next == NULL) { head[i].next = t; }else { p = head[i].next; while (p->next != NULL) p = p->next; p->next = t; } //逆邻接表打十字 if (head[i].to == NULL) { head[i].to = t; return 0; }else { p = head[i].to; while (p->next != NULL) p = p->next; p->next = t; } return 0; } int main() { int i,n; memset (head,0,sizeof (head)); //建图 scanf ("%d",&n); for (i = 0;i < n;i++) { int a,b,w; //输入起点、终点、权重 scanf ("%d%d%d",&a,&b,&w); add3 (a,b,w); } return 0; }
邻接多重表(无向图)
#include <stdio.h> #include <stdlib.h> #include <string.h> //邻接多重表(无向图) struct dot { int i,j; int w; struct dot *inext; struct dot *jnext; }; struct hed { int v; struct dot *next; }head[100]; int add4(int i,int j,int w) { struct dot *t = new dot; struct dot *p = NULL,*tp = NULL; t->i = i; t->j = j; t->w = w; t->inext = NULL; t->jnext = NULL; if (head[i].next == NULL) { head[i].next = t; }else { p = head[i].next; while (p != NULL) { tp = p; if (p->i == i) p = p->inext; else p = p->jnext; } if (tp->i == i) tp->inext = t; else tp->jnext = t; } if (head[j].next == NULL) { head[j].next = t; }else { p = head[j].next; while (p != NULL) { tp = p; if (p->i == j) p = p->inext; else p = p->jnext; } if (tp->i == j) tp->inext = t; else tp->jnext = t; } return 0; } int main() { int i,n; memset (head,0,sizeof (head)); //建图 scanf ("%d",&n); for (i = 0;i < n;i++) { int a,b,w; //输入起点、终点、权重 scanf ("%d%d%d",&a,&b,&w); add4 (a,b,w); } return 0; }
边集数组
#include <stdio.h> #include <stdlib.h> #include <string.h> //边集数组 struct e { int i,j; int w; }eg[100]; int cont; int add5(int i,int j,int w) { eg[cont].i = i; eg[cont].j = j; eg[cont].w = w; return 0; } int main() { int i,n; memset (eg,0,sizeof (eg)); cont = 0; //建图 scanf ("%d",&n); for (i = 0;i < n;i++) { int a,b,w; //输入起点、终点、权重 scanf ("%d%d%d",&a,&b,&w); //有向图无向图皆可 add5 (a,b,w); } return 0; }
边集数组之前向星
#include <stdio.h> #include <stdlib.h> #include <string.h> //前向星 int head[100]; struct e { int to; int fro; int w; }eg[100]; int cont; int add6 (int i,int j,int w) { eg[cont].to = j; eg[cont].fro = head[i]; eg[cont].w = w; head[i] = cont++; return 0; } int main() { int i,n; memset (head,-1,sizeof (head)); cont = 0; //建图 scanf ("%d",&n); for (i = 0;i < n;i++) { int a,b,w; //输入起点、终点、权重 scanf ("%d%d%d",&a,&b,&w); add6 (a,b,w); //无向图加上 add6 (b,a,w); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115647.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...