图的几种存储方式 |
您所在的位置：网站首页 › 节点图绘制方法有哪几种 › 图的几种存储方式 |
图的几种存储方式
|
第一次给501的同学们讲课，所以好好准备了一下。 本博客大多为自己整理的，错误或不妥当之处还望各位多多指正！谢谢了！本博客代码所用例题为SDUT OJ 图的存储专题的第一题-------> https://acm.sdut.edu.cn/onlinejudge3/problems/3116 废话不多说，直接上目录 图的几种存储结构：1、邻接矩阵 2、邻接表 3、链式前向星 4、C++中vector的邻接表实现（补充） （一）邻接矩阵 邻接矩阵是表示顶点之间相邻关系的矩阵。
邻接矩阵的好处： （1）直观、简单、好理解 （2）方便检查任意一对定点间是否存在边 （3）方便找任一顶点的所有“邻接点”（有边直接相连的顶点） （4）方便计算任一顶点的度 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。 对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。 邻接矩阵的局限性：时间复杂度O(n^2），空间复杂度O(n^2) （1）浪费空间。对于稠密图还是很合算的。 但是对于稀疏图（点很多而边很少）有大量无效元素。 （2）浪费时间。要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。 bb这么多，我们直接来以OJ此专题第一题为例 这题二维数组map不能用int，会爆内存，bool可以自己百度，简而言之就是用于逻辑判断，只有true和false两种情况。 bool类型在存储二值变量，或者说只有真假时，更具优势，因为只有0和1即false和true，省空间 （int型的0和1都是4字节，bool都是1字节） #include #include #include bool map[5001][5001]; int main() { int n,m; int u,v; int q; while(~scanf("%d %d",&n,&m)) { memset(map,false,sizeof(map)); while(m--) { scanf("%d %d",&u,&v); map[u][v]=true; } scanf("%d",&q); while(q--) { scanf("%d %d",&u,&v); if(map[u][v]) { printf("Yes\n"); }else { printf("No\n"); } } } return 0; } （二）邻接表 图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。 邻接表的特点如下： （1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。 （2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。 （3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。 （4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。 #include #include #include struct node { int data; struct node *next; }; int main() { int n, u, j, i, v; struct node *p, *a[5050]; while(~scanf("%d", &n)) { for(i = 0; i < n; i++) a[i] = NULL; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { scanf("%d", &u); //审清题意 if(u == 1) { if(a[i] == NULL) { p = (struct node *)malloc(sizeof(struct node)); p -> data = j; p -> next = NULL; a[i] = p; } else { p = (struct node *)malloc(sizeof(struct node)); p -> next = a[i] -> next; p -> data = j; a[i] -> next = p; } } } } int q; scanf("%d", &q); while(q--) { scanf("%d%d", &u, &v); p = a[u]; int flag = 0; while(p) { if(p -> data == v) { flag = 1; break; } p = p -> next; } if(flag) printf("Yes\n"); else printf("No\n"); } } return 0; } （三）链式前向星https://blog.csdn.net/Binary_Heap/article/details/78209086 1. 结构这里用两个东西： 1 结构体数组edge存边，edge[i]表示第i条边, 2 head[i]存以i为起点的第一条边(在edge中的下标) struct edge{ int to; //这条边的终点 int w; //权值 int next; //下一条边的存储下标(默认0) }e[500010];2.增边 若以点u为起点的边新增了一条，在edge中的下标为cnt. 那么edge[++cnt].next=head[u];然后head[u]=cnt. 即每次新加的边作为第一条边，最后倒序遍历 void add(int u, int v, int w) { e[cnt].to = v; e[cnt].w = w; e[cnt].next = head[u];//cnt为边的计数，从1开始计 head[u] = cnt++; //第一条边为当前边 }3. 遍历 遍历以st为起点的边 for(int i=head[st]; i!=0; i=edge[i].next)i 开始为第一条边，每次指向下一条(以0为结束标志) （若下标从0开始，next应初始化-1） 链式前向星主要是用来优化的，可以用来优化BFS，SPFA算法等等。在做最短路的时候一直T就是因为没有用链式前向星存边导致的超时，所以这个坑我先和你们说下。 （四）vector的邻接表（补充）vector是C++STL里面的一个东西，简单的来说就是一个可变长的数组，你可以通过往它里面压入数据来使它变长， 想深入了解的可以自己百度一波，还是以这道题为例： #include #include #include//注意这个头文件不能丢，要么你就去用万能头 using namespace std; #define N 500001 vectorMAP[N];//可以理解为二维的，每个MAP可以包含若干项，这些项是以当前编号点为起点 int main() { int n,m,u,v,i; while(~scanf("%d %d",&n,&m)) { while(m--) { scanf("%d %d",&u,&v); MAP[u].push_back(v);//扩充 } int q; scanf("%d",&q); while(q--) { scanf("%d %d",&u,&v); int len=MAP[u].size(); int flag=0; for(i=0;i |
【本文地址】