图的存储结构(邻接矩阵和邻接表)首先(: )，学习图的一些定义和术语，让我们对图的数据结构有新的见解和认识，理解图结构的知识。 今天我们学习图的记忆结构，图的记忆结构很多，所以我们主要学习邻接矩阵和邻接表。 关于邻接矩阵是使用数组的形式，不称为邻接矩阵、邻接表和十字链结构！
每天一次，防止颓废
1 .邻接矩阵官方术语：
邻接矩阵是表示顶点之间邻接关系的矩阵。 设g=(v，e )为图，其中V={v1，v2，…，vn} [1]。 的邻接矩阵是具有以下性质的n阶方阵：对于有向图来说，邻接矩阵一定是对称的，且主对角线一定是零(这里只讨论有向图) )副对角线不一定是0，有向图也不一定。 在有向图中，任一顶点I的度为第I列(或第I行)所有非零要素的个数，在有向图中顶点I的出度为第I行所有非零要素的个数，入度为第I列所有非零要素的个数。 用邻接矩阵法表示图表一共需要n^2个空间。 有向图的邻接矩阵一定是对称关系，除了对角线为零外，只要记住上三角形或下三角形的数据就可以了，所以只需要n(n-1 )/2个空间。讲人话就是：邻接矩阵和矩阵的三元组表示法有点相似，就是一个顶点，和一个二维数组组合，二维数组的第一个下标表示边的起点，第二下标表示边的终点，有边把这个位置的值赋值为1，没有就赋值为0如下图：.
1.1图的邻接矩阵类型声明： # include stdio.h # include malloc.h # definemaxvex 100//图中的最大顶点个数#define INF 32767//表示为typedefcharvertextytytytextytex //顶点编号VertexType data； //顶点信息} VType； //顶点类型typedef struct graph{ int n，e； //n是实际顶点数，e是实际边数VType vexs[MAXVEX]； //顶点集合int edges[MAXVEX][MAXVEX]； //边的集合(} MatGraph； //图的邻接矩阵类型1.2映射的邻接矩阵运算算法根据邻接矩阵排列a、顶点数n、边数e构成图g的邻接矩阵存储结构。
voidcreategraph(matgraphg，int A[][MAXVEX]，int n，int e ) { int i，j； g.n=n； g.e=e； for(I=0； in； I ) for ) j=0； jn； j ) g.edges[i][j]=A[i][j]； } 1.3销毁图演算算法这里邻接矩阵是图的顺序记忆结构，其内存空间由系统自动分配，不再需要时由系统自动释放。 因此，相应的函数不包含语句。
voiddestroygraph(matgraphg ) /内存空间由系统自动分配，直接结束程序后，{ } 1.4输出图表运算算法被释放，图表g的邻接矩阵存储结构被输出到画面上
voiddispgraph(matgraphg ) { int i，j； for(I=0； ig.n； I ) for(j=0； jg.n； j ) if(g.edges[i][j]INF ) printf )、g.Edges[I][j]； ELSEprintf('%4s”，“”； 打印((n )； }} 1.5求顶点度的运算算法在有向图和有向图中，求顶点度是不同的。 根据定义，求出无向图g中顶点v的度的算法如下。
intdegree1(matgraphg，int v ) /求出无向图的顶点的度(int v，d=0； if(v0||v=g.n ) return -1； //顶点编号错误地输入-1for(I=0； ig.n； I ) if ) g.Edges[v][I]0g.Edges[v][I]INF ) d； //统计第v行不是0也不是的边的数量即度return d； (intdegree2) matgraphg，int v ) /求有向图中顶点的度) int v，d1=0，d2=0，d； if(v0||v=g.n ) return -1； //顶点编号错误地输入-1for(I=0； ig.n； I ) if ) g.Edges[v][I]0g.Edges[v][I]INF ) d1； //统计第v行不是0也不是的边的数量即出度for(I=0； ig.n； I ) if ) g.Edges[I][v]0g.Edges[I][v]
lt;INF) d2++;//统计第v列既不为0也不为∞的边数即入度 d=d1+d2; return d;} 1.6 主函数及效果展示 int main(int argc, char** argv){MatGraph g;int n=5,e=7,i;int A[MAXVEX][MAXVEX]={{0,1,2,6,INF},{INF,0,INF,4,5},{INF,INF,0,INF,3},{INF,INF,INF,0,INF},{INF,INF,INF,7,0}};CreateGraph(g,A,n,e);//建立图7.4图的邻接矩阵printf("图G的存储结构:n"); DispGraph(g);printf("图G中所有顶点的度:n"); printf(" 顶点t度n");for (i=0;i<g.n;i++)printf(" %dt%dn",i,Degree2(g,i));DestroyGraph(g);return 0;} 2.邻接表 邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个带头结点的单链表，把该顶点的所有相邻点串起来。所有的头结点构成一个数组，称为头结点数组，用adjlist表示，第i个单链表adjlist[i]中的结点表示依附于顶点i的边，也就是说头结点数组元素的下标与顶点编号一致。讲人话：就是有一个数组类型的单链表，这个数组的每个结点都代表一个头指针，这个头指针再指向一个单链表，这个单链表用来保存下一个你要指向的顶点（也就是头指针）和权值，对权值不知道的同学看博主上一篇文章
2.1图的邻接表存储结构的类型声明如下： #include <stdio.h>#include <malloc.h>#define MAXVEX 100//图中最大顶点个数#define INF 32767//表示∞typedef char VertexType[10]; //VertexType为字符串类型typedef struct edgenode{ int adjvex; //相邻点序号 int weight; //边的权值 struct edgenode *nextarc; //下一条边的顶点} ArcNode;//每个顶点建立的单链表中边结点的类型typedef struct vexnode{ VertexType data; //存放一个顶点的信息 ArcNode *firstarc; //指向第一条边结点} VHeadNode; //单链表的头结点类型typedef struct { int n,e; //n为实际顶点数,e为实际边数 VHeadNode adjlist[MAXVEX]; //单链表头结点数组} AdjGraph; //图的邻接表类型 2.2 邻接表的创建 void CreateGraph(AdjGraph *&G,int A[][MAXVEX],int n,int e){ int i,j; ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); G->n=n; G->e=e; for (i=0;i<G->n;i++)//邻接表中所有头结点的指针域置空 G->adjlist[i].firstarc=NULL; for (i=0;i<G->n;i++)//检查A中每个元素 for (j=G->n-1;j>=0;j--) if (A[i][j]>0 && A[i][j]<INF) //存在一条边 { p=(ArcNode *)malloc(sizeof(ArcNode)); //创建结点p p->adjvex=j; p->weight=A[i][j]; p->nextarc=G->adjlist[i].firstarc; //头插法插入p G->adjlist[i].firstarc=p; }} 2.3销毁图运算算法邻接表的头结点和边结点都是采用malloc函数分配的，在不再需要时应用free函数释放所有分配的空间。
基本思路：通过adjlist数组遍历每个单链表，释放所有的边结点，最后释放adjlist数组的空间。
将图G的邻接表存储结构输出到屏幕上。
void DispGraph(AdjGraph *G)//输出图的邻接表{ ArcNode *p; int i; for (i=0;i<G->n;i++)//遍历所有的头结点 {printf(" [%2d]",i);p=G->adjlist[i].firstarc;//p指向第一个相邻点if (p!=NULL) printf(" →");while (p!=NULL){ printf(" %d(%d)",p->adjvex,p->weight); p=p->nextarc;//p移向下一个相邻点}printf("n"); }} 2.5求顶点度运算算法对于无向图和有向图，求顶点度有所不同。依据定义，求无向图G中顶点v的度的算法如下：
int Degree1(AdjGraph *G,int v) //求无向图G中顶点v的度{ int d=0; ArcNode *p; if (v<0 || v>=G->n) return -1;//顶点编号错误返回-1 p=G->adjlist[v].firstarc; while (p!=NULL)//统计v顶点的单链表中边结点个数即度 { d++; p=p->nextarc; } return d;}int Degree2(AdjGraph *G,int v) //求有向图G中顶点v的度{ int i,d1=0,d2=0,d; ArcNode *p; if (v<0 || v>=G->n) return -1; //顶点编号错误返回-1 p=G->adjlist[v].firstarc; while (p!=NULL) //统计v的单链表中边结点个数即出度 { d1++; p=p->nextarc; } for (i=0;i<G->n;i++) //统计边结点中adjvex为v的个数即入度 { p=G->adjlist[i].firstarc; while (p!=NULL) { if (p->adjvex==v) d2++; p=p->nextarc; } } d=d1+d2; return d;} 2.6 主函数 int main(int argc, char** argv){AdjGraph *G;int n=5,e=7,i;int A[MAXVEX][MAXVEX]={{0,1,2,6,INF},{INF,0,INF,4,5},{INF,INF,0,INF,3},{INF,INF,INF,0,INF},{INF,INF,INF,7,0}};CreateGraph(G,A,n,e);//建立图7.4图的邻接表printf("图G的存储结构:n"); DispGraph(G);printf("图G中所有顶点的度:n"); printf(" 顶点t度n");for (i=0;i<G->n;i++)printf(" %dt%dn",i,Degree2(G,i));DestroyGraph(G);return 0;}时间关系博主就不展示效果了，把这些代码复制过去就可以了
总结：图的存储我们学习的差不多了，邻接矩阵就是一个存放顶点的数组和一个二维数组组成，二维数组用来下标用来表示顶点与顶点的边连接，有这条边就把这两个下标对于的数组赋值1，没有赋值0，邻接表就是有多个链表，一个用来保存头结点，每个头结点会指向一个链表，这个链表用来存顶点的数组的下标，**注：存头结点的链表是结构体数组类型的。**好了这篇文章博主就学完了，传作不易，点赞关注评论收藏，谢谢啦！！！