用邻接矩阵表示法表示图.doc

第七章图P134用邻接矩阵表示法表示图,除了存储用于表示顶点间相邻关系的邻接矩阵外,通常还需要用一个顺序表来存储顶点信息。其形式说明如下:#definen6       /*图的顶点数*/#definee8       /*图的边(弧)数*/typedefcharvextype;    /*顶点的数据类型*/typedeffloatadjtype;    /*权值类型*/typedefstruct{vextypevexs[n];adjtypearcs[n][n];}graph;P135建立一个无向网络的算法。CREATGRAPH(ga)          /*建立无向网络*/Graph*ga;{inti,j,k;floatw;for(i=0;i<n;i++)ga->vexs[i]=getchar();   /*读入顶点信息,建立顶点表*/for(i=0;i<n;i++)for(j=0;j<n;j++)ga->arcs[i][j]=0;       /*邻接矩阵初始化*/for(k=0;k<e;k++)        /*读入e条边*/(scanf("%d%d%f",&I,&j,&w);  /*读入边(vi,vj)上的权w*/ga->arcs[i][j]=w;ga->arcs[j][i]=w;}}                         /*CREATGRAPH*/P136邻接表的形式说明及其建立算法:typedefstructnode{intadjvex;          /*邻接点域*/structnode*next;    /*链域*/}edgenode;     /*边表结点*/typedefstruct{vextypevertex;    /*顶点信息*/edgenodelink;     /*边表头指针*/}vexnode;         /*顶点表结点*/vexnodega[n];CREATADJLIST(ga)         /*建立无向图的邻接表*/Vexnodega[];{inti,j,k;edgenode*s;for(i=o;i<n;i++=    /*读入顶点信息*/(ga[i].vertex=getchar();ga[i].1ink=NULL;    /*边表头指针初始化*/}for(k=0;k<e;k++=    /*建立边表*/{scanf("%d%d",&i,&j);   /*读入边(vi,vj)的顶点对序号*/s=malloc(sizeof(edgenode));  /*生成邻接点序号为j的表结点*s*/s->adjvex=j;s-->next:=ga[i].Link;ga[i].1ink=s;     /*将*s插入顶点vi的边表头部*/s=malloc(size0f(edgende));  /*生成邻接点序号为i的边表结点*s*/s->adjvex=i;s->next=ga[j].1ink;ga[j].1ink=s;     /*将*s插入顶点vj的边表头部*/}}       /*CREATADJLIST*/P139分别以邻接矩阵和邻接表作为图的存储结构给出具体算法,算法中g、g1和visited为全程量,visited的各分量初始值均为FALSE。intvisited[n]      /*定义布尔