School girl, the C language version of the AOE network data structure you want is here, it's that simple!

Article Directory

AOE critical path programming

Insert picture description here


It is not difficult to find that the biggest feature of the AOE diagram is that there is no loop, and the direction of the directed diagram is always from the source to the sink, and there is one source and sink.

Write Figure 1 as an adjacency matrix file, see file P200G736.TXT, and copy G0.C to AOE.C here, modify the read file name of this program to read the data of the file correctly and construct the diagram.

Analyzing Figure 1 shows that the figure actually has the following path:

V1->V2->V5->V7->V9;
V1->V3->V5->V7->V9;
V1->V2->V5->V8->V9;
V1-> V3->V5- >V8->V9;
V1->V4->V6->V8->V9;

There are 5 paths in total, and the sum of the weights of these 5 paths is the critical path.

Obviously, if the V1 of the above 5 paths is merged into one node, you can see that the result is actually a spanning tree. The nodes on this spanning tree may be duplicates, but if they are all completed, the result must be like this A tree of, such a tree here is a full-path spanning tree. Maybe N textbooks don’t have this title, but to solve the problem by programming, you must first solve the tree, and then sum up each subtree. Weight sum.

It is easy to implement this tree in the C# program. The solution is:

Insert picture description here

Such a tree is actually the result of a special depth-first traversal.

Looking back at the depth-first traversal we have done on ordinary graphs, since there are loops in the graph in the general sense, we need an array like Visited[] to mark the vertices that have been traversed, thereby preventing infinite loops on a loop , But when we analyze the AOE graph, it is not difficult to find: we do not need to mark the vertices that have been traversed, and the depth-first traversal can also smoothly go from the source point to the sink point.

It is not a problem to complete such traversal by hand, so we can write the following program to traverse:

void AOETrav (struct Graph *G,int n)
{
	int i;
	if(G==NULL) return;
	printf("%d\t%s\n",n,G->pV[n]);
	for(i=0;i<G->num;i++)
		if(G->pA[n][i]!=0)
			AOETrav(G,i);
}

Contrast our previous depth-first traversal function:

void DFS(struct Graph *G,int n)
{
	int i;
	if(G==NULL) return;
	if(n<0||n>G->num) return;
	G->Visited[n]=1;
	printf("%s ",G->pV[n]); 
	for(i=0;i<G->num;i++)
		if(G->pA[n][i]!=0&&G->Visited[i]!=1) 
DFS(G,i);
}

Execute the AOE1.c program, the result is:

V1、 V2、V5、V7、 V9、V8、V9、V3、V5、V7、V9、 V8、V9、V4、V6、V8、V9  

Analyzing the procedures and results of Table 1 is not difficult to find:

<1> If the entry parameter n of the AOETrav() function is the parent node of the spanning tree, then the i-th vertex found when entering the next vertex on the 8th line is the child of the nth node;

<2> If the total weight of the nth node is set to w, then the function is the entry parameter:

void AOETrav (struct Graph *G,int n,int w)

After there is such a function, the 9th row of Table 1 is:

AOETrav(G,i, w+G->pA[n][i]);

That is to say: if the weight to the nth vertex is w, then to the i-th vertex after the nth vertex, the total weight is:

w+A[n][i];

Then, we design a parent representation table, press:

Insert picture description here
void AOETrav (struct Graph *G,int n,int w)
{
	int i,nw;
	if(G==NULL) return;
	for(i=0;i<G->num;i++)
		if(G->pA[n][i]!=0)
		{
			nw=w+G->pA[n][i]; 
			printf("%d\t%d\t%s\t%d\n",i,n,G->pV[i],nw);
			AOETrav(G,i,nw);
		}
}

Modify the main() function to start from the 0th vertex, which is:

main()
{
	int i,j;
	struct Stack *S;
	struct Graph *G;
	G=GraphCreat("p200G736.txt");
	printf("顶点名称:\n");
	for(i=0;i<G->num;i++)
		printf("%s\t",G->pV[i]);
	printf("\n邻接矩阵:\n");
	for(i=0;i<G->num;i++) 
		{
		for(j=0;j<G->num;j++)
			printf("%d\t",G->pA[i][j]);
		printf("\n");
		}
	printf("\n");
	printf("ID\tPID\tV\tW\n");
	printf("%d\t%d\t%s\t%d\n",0,-1,G->pV[0],0);
	AOETrav(G,0,0);
}

Run this program, there will be the following results:

Insert picture description here


At this point, the problem of AOE is basically solved. Check Table 6, its maximum weight is 18, see the 4th row and 6th row of the above table, if it is the 4th row, it is V9, the traceback PID=6 to the 3rd row V7, from V7 takes PID=4 back to line 2 V5, then from PID=1 back to V2, takes PID=0 from V2 back to V1, the whole distance is:

V1、V2、V5、V7、V9,The total weight of the whole journey is 18

Similarly, there is a path in line 6:

V1、V3、V5、V8、V9, The weight sum of the whole distance is also 18, which is also a critical path.

It should be noted in Table 6 that since a node in this tree may appear on several sub-trees, the parent node number should look for the nearest node number above.

AOE complete solver

The above solution is feasible for small AOE diagrams, but on large diagrams, it is obvious that Table 6 also needs to be programmed, so a complete AOE processing program also needs to design a sequence table and save the results of Table 6 , And then solve the complete calculation result through the sequence table. This job is left to the students to solve by themselves.

AOE2.c is a program that displays the cumulative total of the weights on each path and the path in a simple way. Please analyze it yourself.