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

blake

1. /* algo7-4.c 输出有向图的一个拓扑序列。实现算法7.12的程序 */
   
2. #include"c1.h"
   
3. #define MAX_NAME 5 /* 顶点字符串的最大长度 */
   
4. typedef int InfoType;
   
5. typedef char VertexType[MAX_NAME]; /* 字符串类型 */
   
6. #include"c7-2.h"
   
7. #include"bo7-2.c"
   
8. 
   
9. void FindInDegree(ALGraph G,int indegree[])
   
10. { /* 求顶点的入度，算法7.12、7.13调用 */
    
11.    int i;
    
12.    ArcNode *p;
    
13.    for(i=0;i<G.vexnum;i++)
    
14.      indegree[i]=0; /* 赋初值 */
    
15.    for(i=0;i<G.vexnum;i++)
    
16.    {
    
17.      p=G.vertices[i].firstarc;
    
18.      while(p)
    
19.      {
    
20.        indegree[p->adjvex]++;
    
21.        p=p->nextarc;
    
22.      }
    
23.    }
    
24. }
    
25. 
    
26. typedef int SElemType; /* 栈类型 */
    
27. #include"c3-1.h"
    
28. #include"bo3-1.c"
    
29. Status TopologicalSort(ALGraph G)
    
30. { /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */
    
31.    /* 否则返回ERROR。算法7.12 */
    
32.    int i,k,count,indegree[MAX_VERTEX_NUM];
    
33.    SqStack S;
    
34.    ArcNode *p;
    
35.    FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */
    
36.    InitStack(&S); /* 初始化栈 */
    
37.    for(i=0;i<G.vexnum;++i) /* 建零入度顶点栈S */
    
38.      if(!indegree[i])
    
39.        Push(&S,i); /* 入度为0者进栈 */
    
40.    count=0; /* 对输出顶点计数 */
    
41.    while(!StackEmpty(S))
    
42.    { /* 栈不空 */
    
43.      Pop(&S,&i);
    
44.      printf("%s ",G.vertices[i].data); /* 输出i号顶点并计数 */
    
45.      ++count;
    
46.      for(p=G.vertices[i].firstarc;p;p=p->nextarc)
    
47.      { /* 对i号顶点的每个邻接点的入度减1 */
    
48.        k=p->adjvex;
    
49.        if(!(--indegree[k])) /* 若入度减为0,则入栈 */
    
50.          Push(&S,k);
    
51.      }
    
52.    }
    
53.    if(count<G.vexnum)
    
54.    {
    
55.      printf("此有向图有回路\n");
    
56.      return ERROR;
    
57.    }
    
58.    else
    
59.    {
    
60.      printf("为一个拓扑序列。\n");
    
61.      return OK;
    
62.    }
    
63. }
    
64. 
    
65. void main()
    
66. {
    
67.    ALGraph f;
    
68.    printf("请选择有向图\n");
    
69.    CreateGraph(&f);
    
70.    Display(f);
    
71.    TopologicalSort(f);
    
72. }

复制代码