关于AOE网的关键路径算法

Ayfkm

1. // 边表结点声明
   
2. typedef struct EdgeNode
   
3. {
   
4.         int adjvex;
   
5.         struct EdgeNode *next;
   
6. }EdgeNode;
   
7. 
   
8. // 顶点表结点声明
   
9. typedef struct VertexNode
   
10. {
    
11.         int in;                        // 顶点入度
    
12.         int data;
    
13.         EdgeNode *firstedge;
    
14. }VertexNode, AdjList[MAXVEX];
    
15. 
    
16. typedef struct
    
17. {
    
18.         AdjList adjList;
    
19.         int numVertexes, numEdges;
    
20. }graphAdjList, *GraphAdjList;
    
21. 
    
22. int *etv, *ltv;
    
23. int *stack2;                        // 用于存储拓扑序列的栈
    
24. int top2;                                // 用于stack2的栈顶指针
    
25. 
    
26. // 拓扑排序算法
    
27. // 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
    
28. Status TopologicalSort(GraphAdjList GL)
    
29. {
    
30.         EdgeNode *e;
    
31.         int i, k, gettop;
    
32.         int top = 0;                // 用于栈指针下标索引
    
33.         int count = 0;                // 用于统计输出顶点的个数
    
34.         int *stack;                        // 用于存储入度为0的顶点
    
35.        
    
36.         stack = (int *)malloc(GL->numVertexes * sizeof(int));
    
37.        
    
38.         for( i=0; i < GL->numVertexes; i++ )
    
39.         {
    
40.                 if( 0 == GL->adjList[i].in )
    
41.                 {
    
42.                         stack[++top] = i;        // 将度为0的顶点下标入栈
    
43.                 }
    
44.         }
    
45.        
    
46.         // 初始化etv都为0
    
47.         top2 = 0;
    
48.         etv = (int *)malloc(GL->numVertexes*sizeof(int));
    
49.         for( i=0; i < GL->numVertexes; i++ )
    
50.         {
    
51.                 etv[i] = 0;
    
52.         }
    
53.         stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
    
54.        
    
55.         while( 0 != top )
    
56.         {
    
57.                 gettop = stack[top--];                // 出栈
    
58.                 // printf("%d -> ", GL->adjList[gettop].data);
    
59.                 stack2[++top2] = gettop;        // 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
    
60.                 count++;                               
    
61.                
    
62.                 for( e=GL->adjList[gettop].firstedge; e; e=e->next )
    
63.                 {
    
64.                         k = e->adjvex;
    
65.                         // 注意：下边这个if条件是分析整个程序的要点！
    
66.                         // 将k号顶点邻接点的入度-1，因为他的前驱已经消除
    
67.                         // 接着判断-1后入度是否为0，如果为0则也入栈
    
68.                         if( !(--GL->adjList[k].in) )       
    
69.                         {
    
70.                                 stack[++top] = k;
    
71.                         }
    
72.                        
    
73.                         if( (etv[gettop]+e->weight) > etv[k] )
    
74.                         {
    
75.                                 etv[k] = etv[gettop] + e->weight;
    
76.                         }
    
77.                 }
    
78.         }
    
79.        
    
80.         if( count < GL->numVertexes )        // 如果count小于顶点数，说明存在环
    
81.         {
    
82.                 return ERROR;
    
83.         }
    
84.         else
    
85.         {
    
86.                 return OK;
    
87.         }
    
88. }
    
89. 
    
90. // 求关键路径，GL为有向图，输出GL的各项关键活动
    
91. void CriticalPath(GraphAdjList GL)
    
92. {
    
93.         EdgeNode *e;
    
94.         int i, gettop, k, j;
    
95.         int ete, lte;
    
96.        
    
97.         // 调用改进后的拓扑排序，求出etv和stack2的值
    
98.         TopologicalSort(GL);
    
99.        
    
100.         // 初始化ltv都为汇点的时间
     
101.         ltv = (int *)malloc(GL->numVertexes*sizeof(int));
     
102.         for( i=0; i < GL->numVertexes; i++ )
     
103.         {
     
104.                 ltv[i] = etv[GL->numVertexes-1];
     
105.         }
     
106.        
     
107.         // 从汇点倒过来逐个计算ltv
     
108.         while( 0 != top2 )
     
109.         {
     
110.                 gettop = stack2[top2--];        // 注意，第一个出栈是汇点
     
111.                 for( e=GL->adjList[gettop].firstedge; e; e=e->next )
     
112.                 {
     
113.                         k = e->adjvex;
     
114.                         if( (ltv[k] - e->weight) < ltv[gettop] )
     
115.                         {
     
116.                                 ltv[gettop] = ltv[k] - e->weight;
     
117.                         }
     
118.                 }
     
119.         }
     
120.        
     
121.         // 通过etv和ltv求ete和lte
     
122.         for( j=0; j < GL->numVertexes; j++ )
     
123.         {
     
124.                 for( e=GL->adjList[j].firstedge; e; e=e->next )
     
125.                 {
     
126.                         k = e->adjvex;
     
127.                         ete = etv[j];
     
128.                         lte = ltv[k] - e->weight;
     
129.                        
     
130.                         if( ete == lte )
     
131.                         {
     
132.                                 printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
     
133.                         }
     
134.                 }
     
135.         }
     
136. }

复制代码

这是小甲鱼求关键路径的算法

本人刚接触数据结构，小白一个，虚心求教，求大神帮忙指导写一个创建AOE网的算法在以上的基础

xueying

学习中

vanentu

辛苦了

vank

辛苦了

逆战时代

LZ好人。。。。。。。。。。。。

EntU

支持楼主！德玛西亚！