数据结构笔记之三十八图的邻接矩阵存储实现.docxVIP

38. 蛤蟆的数据结构笔记之三十八图的邻接矩阵存储实现 本篇名言：“世界上有两种人，一种人，虚度年华；另一种人，过着有意义的生活。在第一种人的眼里，生活就是一场睡眠，如果在他看来，是睡在既温暖又柔和的床铺上，那他便十分心满意足了；在第二种人眼里，可以说，生活就是建立功绩......人就在完成这个功绩中享到自己的幸福。 --别林斯基” 来看下图的邻接存储实现。 1. 邻接矩阵存储原理 对于线性表来说，是一对一的关系，所以用数组或者链表均可简单存放。树结构是一对多的关系，所以我们要将数组和链表的特性结合在一起才能更好的存放。 看如下图1： 因为任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系（内存物理位置是线性的，图的元素关系是平面的）。 考虑到图是由顶点和边或弧两部分组成，合在一起比较困难，那就很自然地考虑到分为两个结构来分别存储。 顶点因为不区分大小、主次，所以用一个一维数组来存储是狠不错的选择。? 而边或弧由于是顶点与顶点之间的关系，一维数组肯定就搞不定了，那我们不妨考虑用一个二维数组来存储。 1.1 邻接矩阵（无向图）? 图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。如下图2 设置两个数组，顶点数组为vertex[4]={V0,V1,V2,V3}，边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边，1表示顶点间存在边)。? 1.2 邻接矩阵（有向图）? 有向图来存放， 如下图3 ? 可见顶点数组vertex[4]={V0,V1,V2,V3}，弧数组arc[4][4]也是一个矩阵，但因为是有向图，所以这个矩阵并不对称，例如由V1到V0有弧，得到arc[1][0]=1，而V0到V1没有弧，因此arc[0][1]=0。 另外有向图是有讲究的，要考虑入度和出度，顶点V1的入度为1，正好是第V1列的各数之和，顶点V1的出度为2，正好是第V1行的各数之和。? 1.3 邻接矩阵（网） 在图的术语中，我们提到了网这个概念，事实上也就是每条边上带有权的图就叫网。如下图4 有了这些概念，是不是顿时感觉很清晰了？让我们来看下代码吧。 2. 代码实现 2.1 定义结构体 结构体包含一个顶点表，邻接矩阵表，以及当前顶点数和边数。 typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边 int numVertexes, numEdges; //图中当前的顶点数和边数 }Graph; 2.2 main 通过creategraph函数来创建图，然后打印图。如下图5 所示： 其中65535表示权值为无穷大。 2.3 locates 输入图的指针，一个字符，判断是否是节点的值。 如果不是则返回-1，如果是则返回是第几个点。 2.4 CreateGraph 建立一个无向网图的邻接矩阵。 输入顶点数和边数。 输入每个顶点的字符，不能为\n符号。 初始化arc 数组，每个值都为65535。 输入每个边的权值，并保存，同时设置矩阵对称。。 2.5 printGraph 依次输出边的权值。 3. 源码 #include stdio.h #include stdlib.h #include curses.h ? typedef char VertexType;??????? ????????//顶点类型应由用户定义 typedef int EdgeType;?????????? ????????//边上的权值类型应由用户定义 ? #define MAXVEX? 100???????????? //最大顶点数，应由用户定义 #define INFINITY??? 65535?????? ????????//用65535来代表无穷大 #define DEBUG ? typedef struct { ????VertexType vexs[MAXVEX];??? ????????//顶点表 ????EdgeType?? arc[MAXVEX][MAXVEX]; ????????//邻接矩阵，可看作边 ????int numVertexes, numEdges;????? //图中当前的顶点数和边数 }Graph; ? //定位 int locates(Graph *g, char ch) { ????int i = 0; ????for(i = 0; i g-numVertexes; i++) ????{ ?????