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

blake

1. /* algo7-5.c 求关键路径。实现算法7.13、7.14的程序 */
   
2. #include"c1.h"
   
3. #define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
   
4. typedef int InfoType;
   
5. typedef char VertexType[MAX_NAME]; /* 字符串类型 */
   
6. #include"c7-2.h"
   
7. #include"bo7-2.c"
   
8. 
   
9. int ve[MAX_VERTEX_NUM]; /* 全局变量(用于算法7.13和算法7.14) */
   
10. 
    
11. void FindInDegree(ALGraph G,int indegree[])
    
12. { /* 求顶点的入度，算法7.12、7.13调用 */
    
13.    int i;
    
14.    ArcNode *p;
    
15.    for(i=0;i<G.vexnum;i++)
    
16.      indegree[i]=0; /* 赋初值 */
    
17.    for(i=0;i<G.vexnum;i++)
    
18.    {
    
19.      p=G.vertices[i].firstarc;
    
20.      while(p)
    
21.      {
    
22.        indegree[p->adjvex]++;
    
23.        p=p->nextarc;
    
24.      }
    
25.    }
    
26. }
    
27. 
    
28. typedef int SElemType; /* 栈类型 */
    
29. #include"c3-1.h"
    
30. #include"bo3-1.c"
    
31. Status TopologicalOrder(ALGraph G,SqStack *T)
    
32. { /* 算法7.13  有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve */
    
33.    /* (全局变量)。T为拓扑序列顶点栈,S为零入度顶点栈。若G无回路,则用栈T */
    
34.    /* 返回G的一个拓扑序列,且函数值为OK,否则为ERROR */
    
35.    int j,k,count,indegree[MAX_VERTEX_NUM];
    
36.    SqStack S;
    
37.    ArcNode *p;
    
38.    FindInDegree(G,indegree);/*对各顶点求入度indegree[0..vernum-1] */
    
39.    InitStack(&S); /* 初始化栈 */
    
40.    for(j=0;j<G.vexnum;++j) /* 建零入度顶点栈S */
    
41.      if(!indegree[j])
    
42.        Push(&S,j); /* 入度为0者进栈 */
    
43.    InitStack(T); /* 初始化拓扑序列顶点栈 */
    
44.    count=0; /* 对输出顶点计数 */
    
45.    for(j=0;j<G.vexnum;++j) /* 初始化ve[]=0 (最小值) */
    
46.      ve[j]=0;
    
47.    while(!StackEmpty(S))
    
48.    { /* 栈不空 */
    
49.      Pop(&S,&j);
    
50.      Push(T,j); /* j号顶点入T栈并计数 */
    
51.      ++count;
    
52.      for(p=G.vertices[j].firstarc;p;p=p->nextarc)
    
53.      { /* 对j号顶点的每个邻接点的入度减1 */
    
54.        k=p->adjvex;
    
55.        if(--indegree[k]==0) /* 若入度减为0,则入栈 */
    
56.          Push(&S,k);
    
57.        if(ve[j]+*(p->info)>ve[k])
    
58.          ve[k]=ve[j]+*(p->info);
    
59.      }
    
60.    }
    
61.    if(count<G.vexnum)
    
62.    {
    
63.      printf("此有向网有回路\n");
    
64.      return ERROR;
    
65.    }
    
66.    else
    
67.      return OK;
    
68. }
    
69. 
    
70. Status CriticalPath(ALGraph G)
    
71. { /* 算法7.14 G为有向网,输出G的各项关键活动 */
    
72.    int vl[MAX_VERTEX_NUM];
    
73.    SqStack T;
    
74.    int i,j,k,ee,el;
    
75.    ArcNode *p;
    
76.    char dut,tag;
    
77.    if(!TopologicalOrder(G,&T)) /* 产生有向环 */
    
78.      return ERROR;
    
79.    j=ve[0];
    
80.    for(i=1;i<G.vexnum;i++) /* j=Max(ve[]) 完成点的值 */
    
81.      if(ve[i]>j)
    
82.        j=ve[i];
    
83.    for(i=0;i<G.vexnum;i++) /* 初始化顶点事件的最迟发生时间(最大值) */
    
84.      vl[i]=j; /* 完成点的最早发生时间 */
    
85.    while(!StackEmpty(T)) /* 按拓扑逆序求各顶点的vl值 */
    
86.      for(Pop(&T,&j),p=G.vertices[j].firstarc;p;p=p->nextarc)
    
87.      {
    
88.        k=p->adjvex;
    
89.        dut=*(p->info); /* dut<j,k> */
    
90.        if(vl[k]-dut<vl[j])
    
91.          vl[j]=vl[k]-dut;
    
92.      }
    
93.    printf(" j  k  dut  ee  el  tag\n");
    
94.    for(j=0;j<G.vexnum;++j) /* 求ee,el和关键活动 */
    
95.      for(p=G.vertices[j].firstarc;p;p=p->nextarc)
    
96.      {
    
97.        k=p->adjvex;
    
98.        dut=*(p->info);
    
99.        ee=ve[j];
    
100.        el=vl[k]-dut;
     
101.        tag=(ee==el)?'*':' ';
     
102.        printf("%2d %2d %3d %3d %3d    %c\n",j,k,dut,ee,el,tag); /* 输出关键活动 */
     
103.      }
     
104.    printf("关键活动为:\n");
     
105.    for(j=0;j<G.vexnum;++j) /* 同上 */
     
106.      for(p=G.vertices[j].firstarc;p;p=p->nextarc)
     
107.      {
     
108.        k=p->adjvex;
     
109.        dut=*(p->info);
     
110.        if(ve[j]==vl[k]-dut)
     
111.          printf("%s→%s\n",G.vertices[j].data,G.vertices[k].data); /* 输出关键活动 */
     
112.      }
     
113.    return OK;
     
114. }
     
115. 
     
116. void main()
     
117. {
     
118.    ALGraph h;
     
119.    printf("请选择有向网\n");
     
120.    CreateGraph(&h);
     
121.    Display(h);
     
122.    CriticalPath(h);
     
123. }

复制代码