首页 > 代码库 > 图的存储结构（精编）
图的存储结构（精编）
一.邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=（V,E）是具有n个顶点的图，顶点的顺序依次是（v0,v1,v2,.....vn-1）,则G的邻接矩阵A是n阶方阵：
若A是无向图，A[i][j]=1,表示i,j之间有一条边，i到j可达且j到i可达。若A是无向图，A[i][j]=1,表示i到j可达，j到i不可达。
邻接矩阵的特点如下：
（1）图的邻接矩阵表示是唯一的；
（2）无向图的邻接矩阵是对称矩阵。压缩方法：存储时只需存储上三角或下三角；
（3）当邻接矩阵是稀疏矩阵时，当图中顶点较多时，可以采用三元组表的方法存储；
（4）对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
对于有向图，第i行（第i列）非零元素的个数正好是第i个顶点的出度（入度）；
局限性：要确定图中有多少条边，必须按行，按列对每个元素进行检测，花费时间代价很大；
1 #define M 最大顶点个数 2 typedef struct 3 { 4 int no;//顶点编号 5 ...//其他信息 6 }vertextype; 7 typedef struct//定义图 8 { 9 int edge[M][M];//邻接矩阵10 int n,e;//顶点数，弧数11 vertextype vexs[M];//存放顶点信息12 }Mgraph;
例如：要存储10个点直接的关系，可以用一个10*10的邻接矩阵来存储，代码如下：
1 #include<stdio.h> 2 #include<string.h> 3 #define M 11 4 typedef struct 5 { 6 int no; 7 }vertextype; 8 typedef struct 9 {10 int edge[M][M];11 int n,e;12 vertextype vexs;13 }Mgraph;14 int main()15 {16 Mgraph A;17 int a,b;18 memset(A.edge,0,sizeof(A.edge));19 A.n=10;20 scanf("%d",&A.e);21 for(int i=1;i<=A.e;i++)22 {23 scanf("%d%d",&a,&b);24 A.edge[a][b]=1;25 }26 for(int i=1;i<=10;i++)27 {28 for(int j=1;j<=10;j++)29 {30 printf("%d ",A.edge[i][j]);31 }32 printf("\n");33 }34 return 0;35 }
二.邻接表存储方法
在我们平时使用邻接矩阵的时候经常会遇到以下三种情况：
1. 对于一个|V|很大的图，无法使用邻接矩阵进行存储。对于256M的内存，所以我们最多能使用的|V| = 8192的邻接矩阵。
2. 对于某些稀疏图或者无根树，每个节点都拥有大小为|V|的数组，但实际使用到的只有很小一部分，造成了很多空间上的浪费。
3. 有时两个点之间不止存在有一条边，这是用邻接矩阵就无法同时表示两条以上的边。
由以上情况我们想到了一种特殊的图存储方式，让每个节点拥有的数组大小刚好就等于它所连接的边数。
邻接表存储方法是一种链式分配和链式分配相结合的存储方法。在邻接表中，对图中的每个顶点建立一个单链表，第i个单链表中的结点依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个单链表上附设一个表头结点。
表结点由三个域组成，adjvex存储与vi邻接的点在图中的位置，nextarc存储下一条边或弧的结点，data存储与边或弧相关的信息如权值。；表头结点由两个域组成，分别指向链表中第一个顶点和存储vi的名或其他信息。
邻接表的特点如下：
（1）表示不唯一；
（2）对于稀疏图，邻接表比邻接矩阵更省空间；
（3）对于无向图，vi对应第i个链表的表结点个数等于顶点得度；
对于有向图，vi对应第i个链表的表结点个数等于顶点的出度，其入度为邻接表中所有adjvex值域为i的边结点数目。
1 typedef struct ANode//弧的结点结构类型 2 { 3 int adjvex;//弧的终点位置 4 sgruct ANode *nextarc;//指向下一条弧的指针 5 }ArcNode; 6 typedef struct VNode//邻接表头结点类型 7 { 8 Vertex data;//顶点信息 9 ArcNode *firstarc;//指向第一条弧10 }Vnode;11 typedef Vnode A[M];//A是邻接表类型12 typedef struct13 {14 A adjlist;//邻接表15 int n,e;16 }Agraph;//图的类型
逆邻接表：就是在有向图的邻接表中，对每个顶点，连接的是指向该顶点的弧。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MaxVertexNum 100 4 typedef char VertexType; 5 typedef struct node //边表节点 6 { 7 int adjvex; 8 node* next; 9 } EdgeNode;10 typedef struct //顶点表节点11 {12 VertexType vertex;13 EdgeNode* firstedge;14 } VertexNode;15 typedef VertexNode AdjList[MaxVertexNum];16 typedef struct17 {18 AdjList adjlist;19 int n,e;20 21 } ALGraph;22 void create(ALGraph*);23 void main()24 {25 ALGraph* G= (ALGraph*)malloc(sizeof(ALGraph));26 create(G);27 for (int i=0; i< G->n; i++)28 {29 printf("%d->",i);30 while(G->adjlist[i].firstedge!=NULL)31 {32 printf("%d->",G->adjlist[i].firstedge->adjvex);33 G->adjlist[i].firstedge=G->adjlist[i].firstedge->next;34 35 }36 printf("\n");37 }38 }39 void create(ALGraph* G)40 {41 int i,j,k,w,v;42 EdgeNode *s;43 printf("读入顶点数和边数");44 scanf("%d,%d",&G->n,&G->e);45 for (i=0; i<G->n; i++)46 {47 fflush(stdin);48 printf("建立顶点表");49 G->adjlist[i].vertex=getchar();50 G->adjlist[i].firstedge=NULL;51 }52 printf("建立边表\n");53 for (k=0; k<G->e; k++)54 {55 printf("读入(vi-vj)的顶点对序号");56 scanf("%d,%d",&i,&j);57 s=(EdgeNode*)malloc(sizeof(EdgeNode));58 s->adjvex=j;59 s->next=G->adjlist[i].firstedge; //插入表头60 G->adjlist[i].firstedge=s;61 s=(EdgeNode*)malloc(sizeof(EdgeNode));62 s->adjvex=i;63 s->next=G->adjlist[j].firstedge;64 G->adjlist[j].firstedge=s;65 66 }67 }
三. 十字链接表存储方法
实际上是邻接表和逆邻接表的结合。在十字邻接表中，每个边结点对应图中的一条边，把每一条边的边结点分别组织到以起始顶点为头结点的的链表和以终点结点为头结点的链表中。
四. 邻接多重表存储方法
邻接多重表(Adjacency Multilist)是无向图的另一中链式存储结构。虽然邻接表是无向图的一种有效的存储结构，在邻接表中容易求顶点和边的各种信息。但是，在邻接表中的每一条边的两个结点分别在不同的链表中。这给某些图的操作带来不便。(如对搜索过的边标记或删除一条边等)邻接多重表的结构和十字链表相似。给每一条边用一个结点表示！
在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。
可见，对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。
因此，除了在边结点增加一个标志域外，邻接多重表所需的存储量和邻接表相同。因此，各种基本操作的实现亦和邻接表相似。
第三第四种不常用，此处暂不做深入探讨。
各位晚安~~
图的存储结构（精编）