当前位置:   article > 正文

邻接矩阵的定义和例子

邻接矩阵
根据图的定义可知,图的 逻辑结构 分为两部分:V和E的集合。因此,用一个一维 数组 存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,称这个二维数组为邻接 矩阵 。邻接矩阵又分为有向图邻接矩阵和 无向图 邻接矩阵。
在图的邻接 矩阵 表示法中:
① 用邻接 矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
图的矩阵
设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:
【例】
下图中 无向图G 5 和 有向图G 6 的邻接 矩阵分别为A1 和A 2 。
网络矩阵
若G是网络,则邻接 矩阵 可定义为:
其中:
w ij 表示边上的权值;
∞表示一个计算机允许的、大于所有边上权值的数。
【例】下面带权图的两种邻接 矩阵分别为A 3 和A 4 。
图的邻接 矩阵 存储结构形式说明
#define MaxVertexNum l00 //最大顶点数,应由用户定义
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
  1. typedef struct{
  2.      VextexType vexs[MaxVertexNum]  //顶点表
  3.      EdeType edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵,可看作边表
  4.      int n,e; //图中当前的顶点数和边数
  5.     } MGragh;
注意:
① 在简单应用中,可直接用二维 数组作为图的邻接 矩阵(顶点表及顶点数等均可省略)。
② 当邻接矩阵中的元素仅表示相应的边是否存在时,EdgeTyPe可定义为值为0和1的 枚举类型
  否则,就可以存放别的信息比如边的权重信息。
无向图的邻接矩阵是 对称矩阵,对规模特大的邻接矩阵可压缩存储。
④邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
⑤建立无向网络的算法。


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/306077
推荐阅读