图 - 图的存储结构 - 邻接矩阵表示法
图的存储表示方法很多 这里介绍两种最常用的方法 至于具体选择哪一种表示法 主要取决于具体的应用和欲施加的操作
为了适合用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 )。.lishixinzhi
lishixinzhi/Article/program/sjjg/201311/23848
