|
图的存储表示方法很多这里介绍两种最常用的方法至于具体选择哪一种表示法主要取决于具体的应用和欲施加的操作 为了适合用C语言描述以下假定顶点序号从开始即图G的顶点集的一般形式是V(G)={v v i …V n } 图的邻接矩阵表示法 图的邻接矩阵表示法 在图的邻接矩阵表示法中 ① 用邻接矩阵表示顶点间的相邻关系 ② 用一个顺序表来存储顶点信息 图的邻接矩阵(Adacency Matrix) 设G=(VE)是具有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 ne; //图中当前的顶点数和边数 }MGragh; 注意 ① 在简单应用中可直接用二维数组作为图的邻接矩阵(顶点表及顶点数等均可省略) ② 当邻接矩阵中的元素仅表示相应的边是否存在时EdgeTyPe可定义为值为和的枚举类型 ③ 无向图的邻接矩阵是对称矩阵对规模特大的邻接矩阵可压缩存储 ④ 邻接矩阵表示法的空间复杂度S(n)=(n ) 建立无向网络的算法 void CreateMGraph(MGraph *G) {//建立无向网的邻接矩阵表示 int ijkw; scanf(%d%d&G>n&G>e); //输入顶点数和边数 for(i=;in;i++) //读人顶点信息建立顶点表 G>vexs[i]=getchar(); for(i=;in;i++) for(j=;jn;j++) G>edges[i][j]=; //邻接矩阵初始化 for(k=;ke;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 |
