用邻接矩阵表示法表示图

1、第七章 图P134 用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：# define n 6         /*图的顶点数*/# define e 8         /*图的边（弧）数*/typedef char vextype;      /*顶点的数据类型*/typedef float adjtype;   

2、0;  /*权值类型*/typedef structvextype vexsn;adjtype arcsnn;graph; P135 建立一个无向网络的算法。CREATGRAPH(ga)            /*建立无向网络*/Graph * ga;int i,j,k;float w;for(i0;i<n;i+ )ga ->vexsigetchar();    /*读入顶点信息，建立顶点表*/for(i0;i<n;i+ ) for(j0

3、;j<n;j+)ga ->arcsij0;         /*邻接矩阵初始化*/for(k0;k<e;k+)          /*读入e条边*/(scanf("ddf",&I,&j,&w);   /*读入边(vi,vj)上的权w */ga ->arcsijw;ga - >arcsjiw;     &#

4、160;                    /*CREATGRAPH*/P136 邻接表的形式说明及其建立算法：typedef struct nodeint adjvex;            /*邻接点域*/struct node * next;      /*

5、链域*/edgenode;      /*边表结点*/typedef structvextype vertex;     /*顶点信息*/edgenode link;       /*边表头指针*/vexnode;           /*顶点表结点*/vexnode gan;CREATADJLIST(ga)     

6、      /*建立无向图的邻接表*/Vexnode ga ;int i,j,k;edgenode * s;for(i=o;i<n;i+     /*读入顶点信息*/(gai.vertexgetchar();gai.1inkNULL;     /*边表头指针初始化*/for(k0;k<e;k+     /*建立边表*/scanf("dd",&i,&j);   

7、 /*读入边(vi , vj)的顶点对序号*/smalloc(sizeof(edgenode);   /*生成邻接点序号为j的表结点*s */s-> adjvexj;s- - >next：gai.Link;gai.1inks;      /*将*s插入顶点vi的边表头部*/smalloc(size0f(edgende);   /*生成邻接点序号为i的边表结点*s */s ->adjvexi;s ->nextgaj.1ink;gaj.1inks;   &

8、#160;  /*将*s插入顶点vj的边表头部*/        /* CREATADJLIST */P139 分别以邻接矩阵和邻接表作为图的存储结构给出具体算法，算法中g、g1和visited为全程量，visited的各分量初始值均为FALSE。int visitedn        /*定义布尔向量visitd为全程量*/Graph g;         

9、60;  /*图g为全程量*/DFS(i)                /*从Vi+1出发深度优先搜索图g，g用邻接矩阵表示*/int i; int j;printf("node：cn" , g.vexsi);   /*访问出发点vi+1 */VisitediTRUE；     /*标记vi+l已访问过*/for (j0;j<n;j+)  

10、    /*依次搜索vi+1的邻接点*/    if(g.arcsij1) (! visitedj)       DFS(j);   /*若Vi+l的邻接点vj+l未曾访问过，则从vj+l出发进行深度优先搜索*/         /*DFS*/vexnode gln    /*邻接表全程量*/    DFSL(i)  

11、    /*从vi+l出发深度优先搜索图g1，g1用邻接表表示*/int i; int j;edgenode * p;printf("node：Cn" ,g1i.vertex);vistitediTRUE;pg1i.1ink;     /*取vi+1的边表头指针*/while(p !NULL)     /*依次搜索vi+l的邻接点*/   if(! Vistitedp ->adjvex)   DFSL(p - >a

12、djvex);   /*从vi+1的未曾访问过的邻接点出发进行深度优先搜索*/   pp - >next;     /*找vi+l的下一个邻接点*/       /* DFSL */P142 以邻接矩阵和邻接表作为图的存储结构，分别给出宽度优先搜索算法。BFS(k) /从vk+l出发宽度优先搜索图g，g用邻接矩阵表示，visited为访问标志向量*/int k; int i,j;SETNULL(Q);    &

13、#160;  /*置空队Q */printf("cn"，g.vexsk);     /*访问出发点vk+l*x/visitedkTRUE;      /*标记vk+l已访问过*/ENQUEUE(Q，K);       /*已访问过的顶点(序号)入队列*/While(!EMPTY(Q)      /*队非空时执行*/iDEQUEUE(Q);   &#

14、160;  /*队头元素序号出队列*/     for(j0;j<n;j+)       if(g.arcsij1)(! visitedj)         printf("cn" , g.vexsj);   /*访问vi+l的未曾访问的邻接点vj+l */         

15、; visitedjTRUE;          ENQUEUE(Q,j);     /*访问过的顶点入队*/              /* BFS */BFSL(k)    /*从vk+l出发宽度优先搜索图g1，g1用邻接表表示*/int k int i;edgenode * p;SETNULL(Q);printf

16、("cn" , g1k.vertex);visitedkTRUE;ENQUEUE(Q,k);while(! EMPTY(Q); iDEQUEUE(Q);    pg1i.1ink        /*取vi+l的边表头指针*/    while(p !NULL)      /*依次搜索vi+l的邻接点*/    if( ! visitedp - >adjvex)  

17、;  /*访问vi+l的未访问的邻接点*/      printf"cn" , g1p - >adjvex.vertex;        visitedp - >adjvexTRUE;        ENQUEUE(Q,p - >adjvex);   /*访问过的顶点入队*/     

18、60;        pp - >next;     /*找vi+l的下一个邻接点*/                  /*BFSL*/P148 在对算法Prim求精之前，先确定有关的存储结构如下：typdef structInt fromvex，endvex；   /*边的起点和终点*/float length；

19、60;    /*边的权值*/ edge；float distnn；     /*连通网络的带权邻接矩阵*/edgeTn-1；     /*生成树*/P149 抽象语句(1)可求精为：for(j=1;j<n;j+)      /*对n-1个蓝点构造候选紫边集*/Tj-1.fromvex1;     /*紫边的起点为红点*/Tj-1.endvexj+1;    &

20、#160; /*紫边的终点为蓝点*/Tj-1.1engthdist0j;     /*紫边长度*/P149 抽象语句(3)所求的第k条最短紫边可求精为：minmax;       /*znax大于任何边上的权值*/for (jk;j<n-1;j+)     /*扫描当前候选紫边集Tk到Tn-2，找最短紫边*/if(Tj.1ength<min)minTj.1ength;mj;     /*记录当前最短紫边的

21、位置*/P149 抽象语句（4）的求精：eTm;TmTk;Tke，   /* Tk和Tm交换*/vTkl.Endvex;     /* v是刚被涂红色的顶点*/P149 抽象语句(5)可求精为：for(jk+1;j<n-1;j+)     /*调整候选紫边集Tk+1到Tn-2*/ddistv-1Tj.endvex-1;    /*新紫边的长度*/if(d<Tj.1ength)      /*新紫边的长度小

22、于原最短紫边*/    Tj.1engthd;     Tj.fromvexv;     /*新紫边取代原最短紫边*/    P150 完整的算法：PRIM()   /*从第一个顶点出发构造连通网络dist的最小生成树，结果放在T中*/int j , k , m , v , min , maxl0000;float d;edge e;for(j=1;j<n;j+)      /*构

23、造初始候选紫边集*/Tj-1.formvex1;     /*顶点1是第一个加入树中的红点*/   Tj-1.endvexj+1;   Tj-1.lengthdistoj;for(k0;k<n-1;k+)      /*求第k条边*/minmax;for(jk;j<n-1;j+)        /*在候选紫边集中找最短紫边*/   if(Tj.1ength<m

24、in)     minTj.1ength;      mj;             /*Tm是当前最短紫边*/    eTm;TmTk;Tke;   /*Tk和Tm交换后，Tk是第k条红色树边*/    vTk.endvex ;        /*

25、 v是新红点*/    for(jk+1;j<n-1;j+)     /*调整候选紫边集*/      ddistv-1Tj.endvex-1;       if(d<Tj.1ength);       Tj.1engthd;        Tj.fromvexv; 

26、                     /* PRIM */P151 Kruskl算法的粗略描述：T(V,);While(T中所含边数<n-1)从E中选取当前最短边(u,v);从E中删去边(u,v);if(u,v)并入T之后不产生回路，将边(u,v)并入T中;P153 迪杰斯特拉算法实现。算法描述如下：#define max 32767       

27、    /*max代表一个很大的数*/void dijkstra (float costn,int v)/*求源点v到其余顶点的最短路径及其长度*/ v1=v-1;for (i=0;i<n;i+)    disti=costv1i;       /*初始化dist*/      if (disti<max)        prei=v; 

28、0;    else prei=0;     prev1=0;for (i=0;i<n;i+)     si=0;            /*s数组初始化为空*/sv1=1;            /*将源点v归入s集合*/for (i=0;i<n;i+)  

29、; min=max;     for (j=0;j<n;j+)        if (!sj && (distj<min)          min=distj;           k=j;      

30、0;                /*选择dist值最小的顶点k+1*/     sk=1;             /*将顶点k+1归入s集合中*/     for (j=0;j<n;j+)      

31、0; if (!sj&&(distj>distk+costkj)          distj=distk+costkj;    /*修改 V-S集合中各顶点的dist值*/            prej=k+1;            /*k+

32、1顶点是j+1顶点的前驱*/                          /*所有顶点均已加入到S集合中*/for (j=0;j<n;j+)          /*打印结果*/   printf("%fn%d",distj,j+1;); 

33、   p=prej;    while (p!=0)         printf("%d",p);          p=prep-1;               P155 弗洛伊德算法可以描述为：A(0)ij=costij;

34、               /cost为图的邻接矩阵A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj其中 k=1,2,.,nP155 弗洛伊德算法实现。算法描述如下：int pathnn;          /*路径矩阵*/void floyd (float An,costn) for (i=0;i<n;i+)  

35、60;        /*设置A和path的初值*/      for (j=0;j<n;j+)         if (costij<max)             pathij=j;       

36、60;  else pathij=0;               Aij=costij;                               for (k=0;

37、k<n;k+)    /*做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/      for (i=0;i<n;i+)        for (j=0;j<n;j+)          if (Aij>(Aik+Akj)   /*修改长度和路径*/    

38、;        Aij=Aik+Akj;              pathij=pathik;                   for (i=0;i<n;i+)    /*输出所有顶点对i,j之间的最短路径长度及路径*/      for (j=0;j<n;j+)         printf ("%f",Aij);      /*输出最短路径的长度*/      next=pathij;   &