如何利用邻接矩阵构建网络

图的存储表示方法很多 这里介绍两种最常用的方法 至于具体选择哪一种表示法 主要取决于具体的应用和欲施加的操作

为了适合用C语言描述 以下假定顶点序号从 开始 即图G的顶点集的一般形式是V(G)={v v i … V n }

图的邻接矩阵表示法

图的邻接矩阵表示法

在图的邻接矩阵表示法中

① 用邻接矩阵表示顶点间的相邻关系

② 用一个顺序表来存储顶点信息

图的邻接矩阵(Adacency Matrix)

设G=(V E)是具有n个顶点的图 则G的邻接矩阵是具有如下性质的n阶方阵

【例】下图中无向图G 和有向图G 的邻接矩阵分别为A l 和A

网络的邻接矩阵

若G是网络 则邻接矩阵可定义为

其中

w ij 表示边上的权值;

∞表示一个计算机允许的 大于所有边上权值的数

【例】下面带权图的两种邻接矩阵分别为A 和A

图的邻接矩阵存储结构形式说明

#define MaxVertexNum l //最大顶点数 应由用户定义

typedef char VertexType; //顶点类型应由用户定义

typedef int EdgeType; //边上的权值类型应由用户定义

typedef struct{

VextexType vexs[MaxVertexNum] //顶点表

EdeType edges[MaxVertexNum][MaxVertexNum];

//邻接矩阵 可看作边表

int n e; //图中当前的顶点数和边数

}MGragh;

注意

① 在简单应用中 可直接用二维数组作为图的邻接矩阵(顶点表及顶点数等均可省略)

② 当邻接矩阵中的元素仅表示相应的边是否存在时 EdgeTyPe可定义为值为 和 的枚举类型

③ 无向图的邻接矩阵是对称矩阵 对规模特大的邻接矩阵可压缩存储

④ 邻接矩阵表示法的空间复杂度S(n)= (n )

建立无向网络的算法

void CreateMGraph(MGraph *G)

{//建立无向网的邻接矩阵表示

int i j k w;

scanf( %d%d &G >n &G >e); //输入顶点数和边数

for(i= ;i n;i++) //读人顶点信息 建立顶点表

G >vexs[i]=getchar();

for(i= ;i n;i++)

for(j= ;j n;j++)

G >edges[i][j]= ; //邻接矩阵初始化

for(k= ;k e;k++){//读入e条边 建立邻接矩阵

scanf( %d%d%d &i &j &w);//输入边(v i v j )上的权w

G >edges[i][j]=w;

G >edges[j][i]=w;

}

}//CreateMGraph

该算法的执行时间是 (n+n +e) 由于e <n )。.lishixin