2021-12-23 [data structure course design] [key path]

Critical path:

Planning, construction process, production process and procedure process are usually regarded as a project. The project is usually divided into several sub projects called "activities". After these "activities" are completed, the project can be completed. AOE net is usually used to represent engineering. AOE net is a weighted directed acyclic graph, in which the vertex represents the EVENT, the arc represents the activity, and the weight represents the duration of the activity. AOE net can be used to estimate the completion time of the project. It can make people understand:

(1) How much time does it take to study a project?
(2) What are the key activities affecting the project progress?

Because some activities in AOE network can be carried out in parallel, from the start point to each vertex, there may be more than one directed path from the start point to the completion point, and the length of these paths may also be different. Although the time required to complete the activities of different paths is different, the project is completed only when all the activities on each path are completed. Therefore, the shortest time required to complete the project is the length of the longest path from the start point to the completion point, that is, the sum of the durations of all activities on this path The length of this path is called critical path.

Example: AOE diagram is as follows:

After the program is executed, it should output:

Key activities: A1, a4, a7, a10, a8, a11

The critical paths are: A1 - > A4 - > A7 - > A10 (or V1 - > V2 - > V5 - > V7 - > V9) and A1 - > A4 - > A8 - > a11 (or V1 - > V2 - > V5 - > V8 - > V9)

The time spent is at least: 18 (time units).

Algorithm design:

1. Use adjacency table to store a weighted directed graph.
2. The graph is topologically sorted, and the earliest occurrence time Ve[i] of events is calculated.
3. According to the sorting result, judge whether there is a directed ring in the graph.
4. Calculate the latest occurrence time Vl[i] of the event according to the inverse topology sequence.
5. Calculate the earliest and latest occurrence time of activities, judge key activities and find out key paths.

flow chart:

Algorithm implementation:

using namespace std;

typedef int Status;
typedef int Boolean; 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAX_NAME 5 
typedef int InfoType;
typedef char VertexType[MAX_NAME];
/* ---------------------------------  Adjacency table storage representation of graph--------------------------------*/
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{         //Table node
	int adjvex;                 //The subscript of the vertex to which the arc points
	struct ArcNode *nextarc;    //Pointer to the next arc 
	InfoType *info;             //Edge weight
typedef struct{
	VertexType data;            //Vertex information
	ArcNode *firstarc;          //The address of the first table node, a pointer to the first arc attached to the vertex
}VNode, AdjList[MAX_VERTEX_NUM];//Adjacency table
typedef struct{                 //chart
	AdjList vertices;
	int vexnum, arcnum;         //Number of vertices and edges
	int kind;                   //Types of Graphs
/* -----------------------------   The adjacency table of the graph needs to be used to store the basic operations--------------------------*/ 
int LocateVex(ALGraph G, VertexType u){ 
  //If there is vertex u in G, the position of the vertex in the graph is returned; Otherwise - 1 is returned
	int i;
	for (i = 0; i < G.vexnum; ++i)
		if (strcmp(u, G.vertices[i].data) == 0)
			return i;
	return -1;

Status CreateGraph(ALGraph &G){ //Create directed net
	int i, j, k;
	int w; // Weight  
	VertexType va, vb;
	ArcNode *p;
    G.kind = 1;//Directed net
    printf("Please enter the number of vertices and edges of the graph(Space separated): ");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	printf("Please enter%d The value of the first vertex(<%d Characters):\n", G.vexnum, MAX_NAME);
	for (i = 0; i < G.vexnum; ++i) {
		scanf("%s", G.vertices[i].data);
		G.vertices[i].firstarc = NULL;
	printf("Please enter each arc in sequence(edge)Weight, arc tail and arc head(Space):\n");
	for (k = 0; k < G.arcnum; ++k) {
		scanf("%d%s%s", &w, va, vb);
		i = LocateVex(G, va); // Arc tail 
		j = LocateVex(G, vb); // Arc head 
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = j;
		p->info = (int *)malloc(sizeof(int));
		*(p->info) = w;
		p->nextarc = G.vertices[i].firstarc; // Insert in header 
		G.vertices[i].firstarc = p;
	return OK;

void Display(ALGraph G){ // Adjacency table G of output graph 
	int i;
	ArcNode *p;
	printf("Directed graph\n");
	printf("%d Vertices:\n", G.vexnum);
	for (i = 0; i < G.vexnum; ++i)
		printf("%s ", G.vertices[i].data);
	printf("\n%d Strip arc(edge):\n", G.arcnum);
	for (i = 0; i < G.vexnum; i++){
		p = G.vertices[i].firstarc;
		while (p){
            printf("%s→%s :%d", G.vertices[i].data, G.vertices[p->adjvex].data, *(p->info));
			p = p->nextarc;
void FindInDegree(ALGraph G, int indegree[]){ // Find the penetration of vertices
	int i;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++)
		indegree[i] = 0; /* Initial value assignment */
	for (i = 0; i < G.vexnum; i++){
		p = G.vertices[i].firstarc;
		while (p){
			p = p->nextarc;
typedef int SElemType; 
/* -----------------------------------   Sequential storage representation of stack-----------------------------------*/
#define STACK_INIT_SIZE 10
typedef struct SqStack{
	SElemType *base; 
	SElemType *top;
	int stacksize;
Status InitStack(SqStack &S){ 
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base)
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
Status StackEmpty(SqStack S){
	if (S.top == S.base)
		return TRUE;
		return FALSE;
Status GetTop(SqStack s,SElemType &e){
        return 0;
    e = *(s.top - 1);
    return 1;

Status Push(SqStack &S, SElemType e){ 
	if (S.top - S.base >= S.stacksize) {
		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S.base)
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	*(S.top)++ = e;
	return OK;
Status Pop(SqStack &S, SElemType &e){ /* If the stack is not empty, delete the top element of S, return its value with e, and return OK; Otherwise, ERROR is returned */
	if (S.top == S.base)
		return ERROR;
	e = *--S.top;
	return OK;

int ve[MAX_VERTEX_NUM], vl[MAX_VERTEX_NUM];//e []: earliest occurrence time vl []: latest occurrence time
bool flag = 0;
vector<string> path;
int top,down;
void dfs(ALGraph G, int u){
	if (G.vertices[u].data == G.vertices[top].data) {//Search to end
		if (flag) cout << "\n Or:\n";
		cout << G.vertices[down].data;	//Output starting point
		for(auto &it:path)	//Traverse output critical path
            cout << it;
        flag = 1;			
	ArcNode* p = G.vertices[u].firstarc;	//Initial edge
	for (; p; p = p->nextarc) {				//ergodic
		int k = p->adjvex;					//The subscript of the vertex to which the arc points
		int dut = *(p->info);				//Weight of arc
		if (ve[u] == vl[k] - dut) {			//This is a key activity
            path.push_back(G.vertices[k].data);		//Record key activities
            dfs(G, k);				//Key activities to continue DFS search for the next node
            path.pop_back();		//to flash back
            path.pop_back();		//to flash back

//Algorithm 7.13
Status TopologicalOrder(ALGraph G, SqStack &T){ 
	int j, k, count, indegree[MAX_VERTEX_NUM],e;
	SqStack S;
	ArcNode *p;
	FindInDegree(G, indegree);
	for (j = 0; j < G.vexnum; ++j) 
		if (!indegree[j])
			Push(S, j);
	GetTop(S, down);	//Record start position
	count = 0; 
	for (j = 0; j < G.vexnum; ++j) 
		ve[j] = 0;	//initialization
	while (!StackEmpty(S)){
		Pop(S, j);
		Push(T, j);
		++count;	//Number of vertices stacked
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){	//Traversal adjacency table
			k = p->adjvex;          //The subscript of the vertex to which the arc points
			if (--indegree[k] == 0) //Reduce the input to zero and put it on the stack
				Push(S, k);
			if (ve[j] + *(p->info) > ve[k])//Topology positive order update max
				ve[k] = ve[j] + *(p->info);
	if (count < G.vexnum){
		printf("This directed network has a loop\n");
		return ERROR;
        GetTop(T, top);//The last node of topology sorting is the end point
        return OK;
//Algorithm 7.14
Status CriticalPath(ALGraph G){
	SqStack T;
	int i, j, k, ee, el;
	ArcNode *p;
	char dut, tag;
	if (!TopologicalOrder(G, T)) // Generate a directed ring 
		return ERROR;
	j = ve[0];
	for (i = 1; i < G.vexnum; i++) //J = value of max (VE []) completion point 
		if (ve[i] > j)
			j = ve[i];
	int maxn = j;
	for (i = 0; i < G.vexnum; i++) // The latest (maximum) occurrence time of the initialization vertex event 
		vl[i] = j; // Earliest occurrence time of completion point 
	while (!StackEmpty(T)) // Find the vl value of each vertex in topological reverse order 
		for (Pop(T, j), p = G.vertices[j].firstarc; p; p = p->nextarc){
			k = p->adjvex;
			dut = *(p->info); // dut<j,k> 
			if (vl[k] - dut < vl[j])
				vl[j] = vl[k] - dut;
	printf(" j  k  dut  ee  el  tag\n");
	for (j = 0; j < G.vexnum; ++j)//Seeking ee,el and key activities 
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
			k = p->adjvex;
			dut = *(p->info);//Edge weight
			ee = ve[j];
			el = vl[k] - dut;
			tag = (ee == el) ? '*' : ' ';
			printf("%2d %2d %3d %3d %3d    %c\n", j, k, dut, ee, el, tag);
	printf("Key activities are:\n");
	for (j = 0; j < G.vexnum; ++j) 
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
			k = p->adjvex;
			dut = *(p->info);
			if (ve[j] == vl[k] - dut)
				printf("%s→%s\n", G.vertices[j].data, G.vertices[k].data); // Output key activities 
	printf("The critical path is:\n");
    printf("\n The minimum time spent is:%d\n", maxn); 
	return OK;
int main(){
	ALGraph h;

Test example:

Add two more:
V1 - > V10 (weight 8)
V10 - > V9 (weight is 10)

Test data:

Please enter the number of vertices and edges of the graph(Space separated): 10 13
 Please enter a value for 10 vertices(<5 Characters):
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
 Please enter each arc in sequence(edge)Weight, arc tail and arc head(Space):
6 v1 v2
4 v1 v3
5 v1 v4
1 v2 v5
1 v3 v5
2 v4 v6
9 v5 v7
7 v5 v8
4 v6 v8
2 v7 v9
4 v8 v9
8 v1 v10
10 v10 v9

Operation results

Directed graph
10 Vertices:
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10
13 Strip arc(edge):
v1→v10 :8v1→v4 :5v1→v3 :4v1→v2 :6
v2→v5 :1
v3→v5 :1
v4→v6 :2
v5→v8 :7v5→v7 :9
v6→v8 :4
v7→v9 :2
v8→v9 :4

v10→v9 :10
 j  k  dut  ee  el  tag
 0  9   8   0   0    *
 0  3   5   0   3
 0  2   4   0   2
 0  1   6   0   0    *
 1  4   1   6   6    *
 2  4   1   4   6
 3  5   2   5   8
 4  7   7   7   7    *
 4  6   9   7   7    *
 5  7   4   7  10
 6  8   2  16  16    *
 7  8   4  14  14    *
 9  8  10   8   8    *
Key activities are:
 The critical path is:
 Minimum time spent: 18


  1. In the process of using the adjacency list to save the map, get familiar with the related operations of the linked list again.
  2. Review the writing and use of stack. The topological sequence is solved by stack.
  3. When conducting topological sorting, master the calculation of node degree (in degree) and learn the application of topological order: use topological sorting to calculate the earliest occurrence time.
  4. Review the writing and use of stack. The topological order sequence is stored on the stack, and the topological reverse order sequence is obtained when it is out of the stack. The calculation of the latest occurrence time is solved by topological reverse order.
  5. Review the depth first search on the map. Use DFS to output critical paths.


[1] Yan Weimin, WU Weimin Data structure (C language version) [M]. Beijing: Tsinghua University Press, April 1997

Keywords: Algorithm data structure Graph Theory

Added by bigger on Thu, 23 Dec 2021 14:18:01 +0200