数据结构笔记

38.蛤蟆的数据结构笔记之三十八图的邻接矩阵存储实现本篇名言：“世界上有两种人，一种人，虚度年华；另一种人，过着有意义的生活。在第一种人的眼里，生活就是一场睡眠，如果在他看来，是睡在既温暖又柔和的床铺上，那他便十分心满意足了；在第二种人眼里，可以说，生活就是建立功绩 人就在完成这个功绩中享到自己的幸福。--别林斯基”来看下图的邻接存储实现。邻接矩阵存储原理对于线性表来说，是一对一的关系，所以用数组或者链表均可简单存放。树结构是一对多的关系，所以我们要将数组和链表的特性结合在一起才能更好的存放。看如下图1：GrBGDGrBGD因为任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系（内存物理位置是线性的，图的元素关系是平面的）。考虑到图是由顶点和边或弧两部分组成，合在一起比较困难，那就很自然地考虑到分为两个结构来分别存储。顶点因为不区分大小、主次，所以用一个一维数组来存储是狠不错的选择。而边或弧由于是顶点与顶点之间的关系，一维数组肯定就搞不定了，那我们不妨考虑用一个二维数组来存储。邻接矩阵（无向图）图的邻接矩阵（AdjacencyMatrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。如下图2V2设置两个数组，顶点数组为vertex[4]={V0,Vl,V2,V3}，边数组arc[4][4]为对称矩阵（V2设置两个数组，顶点数组为vertex[4]={V0,Vl,V2,V3}，边数组arc[4][4]为对称矩阵（0表示不存在顶点间的边，1表示顶点间存在边）。VIIiv21V3VIJftV0VIV2V3V0111VI110V211:1V3101邻接矩阵（有向图）有向图来存放，如下图有向图来存放，如下图3可见顶点数组vertex[4]={V0,Vl,V2,V3}，弧数组arc[4][4]也是一个矩阵，但因为是有向图，所以这个矩阵并不对称，例如由VI到V0有弧，得到arc[1][0]=1,而V0到VI没有弧，因此arc[O][l]=O。另外有向图是有讲究的，要考虑入度和出度，顶点VI的入度为1，正好是第VI列的各数之和，顶点V1的出度为2,正好是第V1行的各数之和。邻接矩阵（网）在图的术语中，我们提到了网这个概念，事实上也就是每条边上带有权的图就叫网如下图4

有了这些概念，是不是顿时感觉很清晰了？让我们来看下代码吧。代码实现2.1定义结构体结构体包含一个顶点表，邻接矩阵表，以及当前顶点数和边数。typedefstruct{VertexTy vexsMAXVEX];/顶点表arcMAXVEX]MAXVEX];/邻接矩阵，可看作边intnumVertexes,numEdges;/图中当前的顶点数和边数}Graph;2.2main通过creategraph函数来创建图，然后打印图。如下图5所示:■ F;\VS2012_ZHIZUO\CCC\Debug\CCC.exe\LZ3齣人：辱yidj〉上戌卜枚i,10下标j和权值=辅A丈Cvi,vj＞上的下标下标j和权值=15輸人边上的F标i,1其中65535表示权值为无穷大。locates输入图的指针，一个字符，判断是否是节点的值如果不是则返回-1，如果是则返回是第几个点。CreateGraph建立一个无向网图的邻接矩阵。输入顶点数和边数。输入每个顶点的字符，不能为\n符号。初始化arc数组，每个值都为65535。输入每个边的权值，并保存，同时设置矩阵对称。printGraph依次输出边的权值。

源码#include<stdio.h>#include<stdlib.h>#include<curses.h>typedefcharVertexType;typedefintEdgeType;用户定义typedefcharVertexType;typedefintEdgeType;用户定义//顶点类型应由用户定义//边上的权值类型应由#defineMAXVEX100#defineINFINITY#defineMAXVEX100#defineINFINITY65535//最大顶点数，应由用户定义//用65535来代表无穷大#defineDEBUGtypedefstruct{//顶点表//邻接矩阵，可看作边//顶点表//邻接矩阵，可看作边//图中当前的顶点数和边数EdgeTypearc[MAXVEX][MAXVEX]intnumVertexes,numEdges;}Graph;//定位intlocates(Graph*g,charch){inti=0;for(i=0;i<g->numVertexes;i++){if(g->vexs[i]==ch){break;}}if(i>=g->numVertexes){return-1;}returni;}//建立一个无向网图的邻接矩阵表示voidCreateGraph(Graph*g)inti,j,k,w;printf("输入顶点数和边数：\n");scanf("%d,%d",&(g->numVertexes),&(g->numEdges));#ifdefDEBUGprintf("%d%d\n",g->numVertexes,g->numEdges);#endiffor(i=0;i<g->numVertexes;i++){g->vexs[i]=getchar();while(g->vexs[i]=='\n'){g->vexs[i]=getchar();}}#ifdefDEBUGfor(i=0;i<g->numVertexes;i++){printf("%c",g->vexs[i]);}printf("\n");#endiffor(i=0;i<g->numEdges;i++){for(j=0;j<g->numEdges;j++){g->arc[i][j]=INFINITY;//邻接矩阵初始化}}for(k=0;k<g->numEdges;k++){charp,q;printf("输入边(vi,vj)上的下标i,下标j和权值:\n");p=getchar();while(p=='\n'){p=getchar();}q=getchar();while(q=='\n'){q=getchar();}scanf("%d",&w);intm=-1;intn=-1;m=locates(g,p);n=locates(g,q);if(n==-1||m==-1){fprintf(stderr,"thereisnothisvertex.\n");return;}//getchar();g->arc[m][n]=w;g->arc[n][m]=g->arc[m][n];//因为是无向图，矩阵对称}}//打印图voidprintGraph(Graphg){inti,j;for(i=0;i<g.numVertexes;i++){for(j