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


		#define MaxVertexNum l00 //最大顶点数，应由用户定义
 
typedef char VertexType； //顶点类型应由用户定义
 
typedef int EdgeType； //边上的权值类型应由用户定义
 
typedef struct{
 
VextexType vexs[MaxVertexNum] //顶点表
 
EdeType edges[MaxVertexNum][MaxVertexNum];
 
//邻接矩阵，可看作边表
 
int n，e； //图中当前的顶点数和边数
 
}MGragh；
 
注意：
 
　 ① 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。
 
　 ② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。
 
　 ③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
 
　 ④ 邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
 
5．建立无向网络的算法。
 
void CreateMGraph(MGraph *G)
 
{//建立无向网的邻接矩阵表示
 
int i，j，k，w；
 
scanf("％d％d"，&G->n，&G->e)； //输入顶点数和边数
 
for(i=0;i<G->n；i++) //读人顶点信息，建立顶点表
 
G->vexs[i]=getchar()；
 
for(i=0；i<G->n；i++)
 
for(j=0；j<G->n；j++)
 
G->edges[i][j]=0； //邻接矩阵初始化
 
for(k=0；k<G->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
 
该算法的执行时间是0(n+n 2 +e)。由于e<n 2 ，算法的时间复杂度是0(n 2 )。

补充：综合编程 , 其他综合 ,