本文主要是介绍月球美容计划之图的储存结构汇总，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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;elsep = p->jnext;}if (tp->i == i)tp->inext = t;elsetp->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;elsep = p->jnext;}if (tp->i == j)tp->inext = t;elsetp->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;
}
这篇关于月球美容计划之图的储存结构汇总的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
