C语言数据结构-algo7-3.c

blake

1. /* algo7-3.c 实现算法7.10、7.11的程序 */
   
2. #include"c1.h"
   
3. #define MAX_NAME 2 /* 顶点字符串的最大长度+1 */
   
4. typedef int InfoType;
   
5. typedef char VertexType[MAX_NAME]; /* 字符串类型 */
   
6. #include"c7-2.h"
   
7. #include"bo7-2.c"
   
8. 
   
9. int count; /* 全局量count对访问计数 */
   
10. int low[MAX_VERTEX_NUM];
    
11. 
    
12. void DFSArticul(ALGraph G,int v0)
    
13. { /* 从第v0个顶点出发深度优先遍历图G，查找并输出关节点。算法7.11 */
    
14.    int min,w;
    
15.    ArcNode *p;
    
16.    visited[v0]=min=++count; /* v0是第count个访问的顶点 */
    
17.    for(p=G.vertices[v0].firstarc;p;p=p->nextarc) /* 对v0的每个邻接顶点检查 */
    
18.    {
    
19.      w=p->adjvex; /* w为v0的邻接顶点 */
    
20.      if(visited[w]==0) /* w未曾访问，是v0的孩子 */
    
21.      {
    
22.        DFSArticul(G,w); /* 返回前求得low[w] */
    
23.        if(low[w]<min)
    
24.          min=low[w];
    
25.        if(low[w]>=visited[v0])
    
26.          printf("%d %s\n",v0,G.vertices[v0].data); /* 关节点 */
    
27.      }
    
28.      else if(visited[w]<min)
    
29.        min=visited[w]; /* w已访问，w是v0在生成树上的祖先 */
    
30.    }
    
31.    low[v0]=min;
    
32. }
    
33. 
    
34. void FindArticul(ALGraph G)
    
35. { /* 连通图G以邻接表作存储结构，查找并输出G上全部关节点。算法7.10 */
    
36.    /* 全局量count对访问计数。 */
    
37.    int i,v;
    
38.    ArcNode *p;
    
39.    count=1;
    
40.    low[0]=visited[0]=1; /* 设定邻接表上0号顶点为生成树的根 */
    
41.    for(i=1;i<G.vexnum;++i)
    
42.      visited[i]=0; /* 其余顶点尚未访问 */
    
43.    p=G.vertices[0].firstarc;
    
44.    v=p->adjvex;
    
45.    DFSArticul(G,v); /* 从第v顶点出发深度优先查找关节点 */
    
46.    if(count<G.vexnum) /* 生成树的根有至少两棵子树 */
    
47.    {
    
48.      printf("%d %s\n",0,G.vertices[0].data); /* 根是关节点，输出 */
    
49.      while(p->nextarc)
    
50.      {
    
51.        p=p->nextarc;
    
52.        v=p->adjvex;
    
53.        if(visited[v]==0)
    
54.          DFSArticul(G,v);
    
55.      }
    
56.    }
    
57. }
    
58. 
    
59. void main()
    
60. {
    
61.    int i;
    
62.    ALGraph g;
    
63.    printf("请选择无向图\n");
    
64.    CreateGraph(&g);
    
65.    printf("输出关节点：\n");
    
66.    FindArticul(g);
    
67.    printf(" i G.vertices[i].data visited[i] low[i]\n");
    
68.    for(i=0;i<g.vexnum;++i)
    
69.      printf("%2d %9s %14d %8d\n",i,g.vertices[i].data,visited[i],low[i]);
    
70. }

复制代码