图的存储结构与方法（二）

图为网（权值图）时，邻接矩阵的表达方法：

网（权值图）

用邻接矩阵表示：

• 在实际中，往往利用其最小值，所以，不存在的边的数值用无穷大表示

图的邻接矩阵存储的实现方法

• 算法分为两部分：主算法和子算法

• 无向网的主算法

Status CreatGraph(Mgraph&G){ (主算法，生成图)

scanf( &G.kind); (读入要生成图的种类)

switch (G.kind) {

case DG: return CreateDG(G);(生成有向图 G)

case DN: return CreateDN(G);(生成有向网 G)

case UDG: return CreateUDG(G);(生成无向图 G)

case UDN: return CreateUDN(G):(生成无向网 G)

default : reaturn ERROR;

}

}//CreateGraph

• 无向网的子算法:

Status CreateUDN(MGraph &G) {

scanf(&G.vexnum,&G.arcnum;&lnclnfo); (INFO 为 0 则弧无其他信息)

for(i=0; i<G.vexnum;++i) scanf(&G.vexs[i]);(构造顶点向量)

for (i=0; i<G.vexnum;++i ) (初始化邻接矩阵)

for(j=0; j<G.vexnum;++j) G.arcs[i][] ={INFINTY,NULL};

for(k=0; k<G. arcnum;++k ) { (构造邻接矩阵)

scanf(&v1,&v2,&w);(输入一条边关联的顶点及权值)

i=LocateVex(G,v1);

j= LocateVex(G,v2);(确定顶点在 G 中位置)

G.arcs[i][j].adj=w;(边(v1,v2)的权值)

if(lnclnfo)Input(G.arcs[i][j].info);(若边含有相关信息，则输入)

G.arcs[j][i]=G.arcs[i][j]; (置(v1,v2 )的对称边力(v2,v1))

}

return OK;

}//CreateUDN