Storage structure and method of graph (II)

The picture shows the net （ Weight graph ） when , The expression of adjacency matrix ：

network （ Weight graph ）

It's represented by adjacency matrix ：

• 
  
  In practice, , Often use its minimum , therefore , The values of nonexistent edges are represented by infinity

Implementation method of adjacency matrix storage of graph

• 
  
  The algorithm is divided into two parts ： Main algorithm and sub Algorithm

• 
  
  The main algorithm of undirected network

Status CreatGraph(Mgraph&G){ ( Main algorithm , Generate graph )

scanf( &G.kind); ( Read in the type of graph to be generated )

switch (G.kind) { 

case DG: return CreateDG(G);( Generate directed graph G) 

case DN: return CreateDN(G);( Generate directed nets G) 

case UDG: return CreateUDG(G);( Generate an undirected graph G)

 case UDN: return CreateUDN(G):( Generate undirected nets G) 

default : reaturn ERROR;

}

}//CreateGraph 

• The sub algorithm of undirected net :

Status CreateUDN(MGraph &G) {

scanf(&G.vexnum,&G.arcnum;&lnclnfo); (INFO by 0 Then the arc has no other information )

for(i=0; i<G.vexnum;++i) scanf(&G.vexs[i]);( Construct vertex vector )

for (i=0; i<G.vexnum;++i ) ( Initialize adjacency matrix ) 

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

for(k=0; k<G. arcnum;++k ) { ( Construct adjacency matrix ) 

scanf(&v1,&v2,&w);( Enter the vertex and weight associated with an edge )

i=LocateVex(G,v1); 

j= LocateVex(G,v2);( Make sure the vertex is at G Middle position ) 

G.arcs[i][j].adj=w;( edge (v1,v2) A weight )

if(lnclnfo)Input(G.arcs[i][j].info);( If the edge contains relevant information , Then input. ) 

G.arcs[j][i]=G.arcs[i][j]; ( Set up (v1,v2 ) Symmetric edge force of (v2,v1))

}

return OK;

}//CreateUDN