这个算法来求关键路径,其实就是利用拓扑排序,首先求出,每个节点最晚开始时间,再倒退求每个最早开始的时间。
从而算出活动最早开始的时间和最晚开始的时间,如果这两个时间相等,则为关键路径。
时间复杂度为O(n+e)
int topSort(Graph *g){
EdgeNode *e;
int i,k,gettop;
int top = 0 ;
int count = 0;
int *stack;
stack = (int *)malloc(g->numVertexes * sizeof(int));
for(i=0;i<g->numVertexes;i++){
if(g->headlist[i].in == 0) //把入度为0的,即没有入度的点入栈
stack[++top] = i;
}
top2 = 0;
etv = (int *)malloc(g->numVertexes*sizeof(int));
for(i=0;i<g->numVertexes;i++){
etv[i] = 0;
}
stack2=(int *)malloc(g->numVertexes*sizeof(int));
while(top){
gettop = stack[top--];
printf("%d ",gettop);
count++;
stack2[++top2] = gettop;
for(e = g->headlist[gettop].fnode; e ; e=e->next){ //一次遍历链表,减少各个子节点的入度
k = e->data;
if(!(--g->headlist[k].in))
stack[++top] = k;
if((etv[gettop]+e->weight)>etv[k]) //选取最大值
etv[k] = etv[gettop]+e->weight;
}
}
if(count < g->numVertexes)
return ERROR;
else
return OK;
}
int critical(Graph *g){
EdgeNode *e;
int i,gettop,k,j;
int ete,lte;
topSort(g);
printf("\n-------------------------------------------\n");
for(i=0;i<g->numVertexes;i++){
printf("%d ",etv[i]);
}
printf("\n-------------------------------------------\n");
ltv = (int *)malloc(sizeof(int)*g->numVertexes);
for(i=0;i<g->numVertexes;i++){
ltv[i] = etv[g->numVertexes-1];
}
while(top2!=0){
gettop = stack2[top2--];
for(e = g->headlist[gettop].fnode;e;e = e->next){
k = e->data;
if(ltv[k]-e->weight < ltv[gettop]){
ltv[gettop] = ltv[k] - e->weight;
}
}
}
for(i=0;i<g->numVertexes;i++){
printf("%d ",ltv[i]);
}
printf("\n-------------------------------------------\n");
printf("\n");
for(j=0;j<g->numVertexes;j++){
for(e=g->headlist[j].fnode; e; e=e->next){
k = e->data;
ete = etv[j];//活动最早
lte = ltv[k] - e->weight;//活动最迟
if(ete == lte)
printf("<v%d v%d>length:%d\n",g->headlist[j].data,g->headlist[k].data,e->weight);
}
}
return 1;
}
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #define MAX 9
5 #define ERROR 1
6 #define OK 0
7 typedef struct edgeNode{
8 int data;
9 int weight;
10 struct edgeNode *next;
11 }EdgeNode;
12 typedef struct headNode{
13 int in;
14 int data;
15 EdgeNode *fnode;
16 }HeadNode,HeadList[MAX];
17 typedef struct{
18 HeadList headlist;
19 int numEdges,numVertexes;
20 }Graph,*graph;
21
22 int *etv,*ltv;
23 int *stack2;
24 int top2;
25
26 void initialGraph(Graph *g);
27 void headinfo(Graph *g,int in,int node);
28 void linkinfo(Graph *g,int node,int link,int weight);
29 void printGraph(Graph *g);
30 int topSort(Graph *g);
31 int critical(Graph *g);
32
33 int main(){
34 Graph *g = (Graph *)malloc(sizeof(Graph));
35 g->numEdges = 0;
36 g->numVertexes = 0;
37 initialGraph(g);
38 printGraph(g);
39
40 critical(g);
41 //topSort(g);
42
43 getchar();
44 return 0;
45 }
46 int critical(Graph *g){
47 EdgeNode *e;
48 int i,gettop,k,j;
49 int ete,lte;
50
51 topSort(g);
52 printf("\n-------------------------------------------\n");
53 for(i=0;i<g->numVertexes;i++){
54 printf("%d ",etv[i]);
55 }
56 printf("\n-------------------------------------------\n");
57 ltv = (int *)malloc(sizeof(int)*g->numVertexes);
58 for(i=0;i<g->numVertexes;i++){
59 ltv[i] = etv[g->numVertexes-1];
60 }
61
62 while(top2!=0){
63 gettop = stack2[top2--];
64 for(e = g->headlist[gettop].fnode;e;e = e->next){
65 k = e->data;
66 if(ltv[k]-e->weight < ltv[gettop]){
67 ltv[gettop] = ltv[k] - e->weight;
68 }
69 }
70 }
71
72 for(i=0;i<g->numVertexes;i++){
73 printf("%d ",ltv[i]);
74 }
75 printf("\n-------------------------------------------\n");
76 printf("\n");
77 for(j=0;j<g->numVertexes;j++){
78 for(e=g->headlist[j].fnode; e; e=e->next){
79 k = e->data;
80 ete = etv[j];//活动最早
81 lte = ltv[k] - e->weight;//活动最迟
82 if(ete == lte)
83 printf("<v%d v%d>length:%d\n",g->headlist[j].data,g->headlist[k].data,e->weight);
84 }
85 }
86 return 1;
87 }
88
89 int topSort(Graph *g){
90 EdgeNode *e;
91 int i,k,gettop;
92 int top = 0 ;
93 int count = 0;
94 int *stack;
95 stack = (int *)malloc(g->numVertexes * sizeof(int));
96 for(i=0;i<g->numVertexes;i++){
97 if(g->headlist[i].in == 0) //把入度为0的,即没有入度的点入栈
98 stack[++top] = i;
99 }
100
101 top2 = 0;
102 etv = (int *)malloc(g->numVertexes*sizeof(int));
103 for(i=0;i<g->numVertexes;i++){
104 etv[i] = 0;
105 }
106 stack2=(int *)malloc(g->numVertexes*sizeof(int));
107
108 while(top){
109 gettop = stack[top--];
110 printf("%d ",gettop);
111 count++;
112 stack2[++top2] = gettop;
113
114 for(e = g->headlist[gettop].fnode; e ; e=e->next){ //一次遍历链表,减少各个子节点的入度
115 k = e->data;
116 if(!(--g->headlist[k].in))
117 stack[++top] = k;
118 if((etv[gettop]+e->weight)>etv[k]) //选取最大值
119 etv[k] = etv[gettop]+e->weight;
120 }
121 }
122 if(count < g->numVertexes)
123 return ERROR;
124 else
125 return OK;
126 }
127
128 void printGraph(graph g){
129 int i;
130 printf("vertex:%d,edges:%d\n",g->numVertexes,g->numEdges);
131 EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
132 for(i=0;i<MAX;i++){
133 printf("[in:%d]%d",g->headlist[i].in,g->headlist[i].data);
134 e = g->headlist[i].fnode;
135 while(e != NULL){
136 printf("->%d(%d)",e->data,e->weight);
137 e = e->next;
138 }
139 printf("\n");
140 }
141 free(e);
142 }
143 void initialGraph(Graph *g){
144 headinfo(g,0,0);
145 linkinfo(g,0,2,4);
146 linkinfo(g,0,1,3);
147
148 headinfo(g,1,1);
149 linkinfo(g,1,3,5);
150 linkinfo(g,1,4,6);
151
152 headinfo(g,1,2);
153 linkinfo(g,2,3,8);
154 linkinfo(g,2,5,7);
155
156 headinfo(g,2,3);
157 linkinfo(g,3,4,3);
158
159 headinfo(g,2,4);
160 linkinfo(g,4,6,9);
161 linkinfo(g,4,7,4);
162
163 headinfo(g,1,5);
164 linkinfo(g,5,7,6);
165
166 headinfo(g,1,6);
167 linkinfo(g,6,9,2);
168
169 headinfo(g,2,7);
170 linkinfo(g,7,8,5);
171
172 headinfo(g,1,8);
173 linkinfo(g,8,9,3);
174
175 headinfo(g,2,9);
176 }
177 void headinfo(Graph *g,int in,int node){
178 g->headlist[node].in = in;
179 g->headlist[node].data = node;
180 g->headlist[node].fnode = NULL;
181 g->numVertexes++;
182 }
183 void linkinfo(Graph *g,int node,int link,int weight){
184 EdgeNode *en = (EdgeNode *)malloc(sizeof(EdgeNode));
185 if(g->headlist[node].fnode != NULL){
186 en->next = g->headlist[node].fnode;
187 }else{
188 en->next = NULL;
189 }
190 g->headlist[node].fnode = en;
191 en->data = link;
192 en->weight = weight;
193 g->numEdges++;
194 }