有向无环图的关键路径（C语言）

谁践踏了优雅 2022-10-15 00:37 145阅读 0赞

用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间，这样构造出来的有向无环图称为边表示活动的网简称AOE-网。

AOE-网中存在唯一的、入度为0的顶点，称为源点，存在唯一的、出度为0的顶点，称为汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径称为关键路径。关键路径上的活动称为关键活动。

代码：

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VER_NUM 2000
    
    typedef enum {
         DG, UDG, DN, UDN }GraphKind;
    
    typedef struct ArcNode{
        
    	int adjvex;
    	struct ArcNode* nextarc;
    	int weight;
    }ArcNode;
    
    typedef struct {
        
    	int data;
    	ArcNode* firstarc;
    }VexNode;
    
    typedef struct {
        
    	VexNode vertex[MAX_VER_NUM];
    	int num_arc, num_vex;
    	GraphKind kind;
    }AdjList;
    
    typedef struct {
        
    	int data[MAX_VER_NUM];
    	int top;
    }Stack;
    
    Stack InitStack();     //初始化栈
    void PushStack(Stack* S, int v);   //入栈
    void PopStack(Stack* S, int* v);   //出栈
    int LocateVertex(AdjList A, int v);   //找到顶点位置
    AdjList* CreateGraph(int n, int m);   //创建有向网
    void FindID(AdjList A, int indegree[MAX_VER_NUM]);   //求入度
    int TopoOrder(AdjList A, Stack* T);   //将最早时间填入ve数列中，将拓扑序列填入T栈中
    int CriticalPath(AdjList A);   //关键路径
    
    
    int main()
    {
        
    	int n, m;
    	scanf("%d%d", &n, &m);
    	AdjList* A;
    	A = CreateGraph(n, m);
    	CriticalPath(*A);
    	return 0;
    }
    
    Stack InitStack()
    {
           //初始化栈
    	Stack S;
    	S.top = -1;
    	return S;
    }
    
    void PushStack(Stack* S, int v)
    {
           //入栈
    	if (S->top == MAX_VER_NUM - 1) {
        
    		return;
    	}
    	S->top++;
    	S->data[S->top] = v;
    }
    
    void PopStack(Stack* S, int* v)
    {
           //出栈
    	if (S->top == -1) {
        
    		return;
    	}
    	*v = S->data[S->top];
    	S->top--;
    }
    
    int LocateVertex(AdjList A, int v)
    {
           //找到顶点位置
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (A.vertex[i].data == v) {
        
    			return i;
    		}
    	}
    	return -1;
    }
    
    AdjList* CreateGraph(int n, int m)
    {
           //创建有向网
    	AdjList* A;
    	A = (AdjList*)malloc(sizeof(AdjList));
    	if (A == NULL) {
        
    		return NULL;
    	}
    	A->kind = DN;
    	A->num_vex = n;
    	A->num_arc = m;
    	for (int i = 0; i < A->num_vex; i++) {
        
    		scanf("%d", &A->vertex[i].data);
    		A->vertex[i].firstarc = NULL;
    	}
    	int v1, v2, w, loc1;
    	for (int i = 0; i < A->num_arc; i++) {
        
    		scanf("%d%d%d", &v1, &v2, &w);
    		ArcNode* tmp;
    		tmp = (ArcNode*)malloc(sizeof(ArcNode));
    		if (tmp == NULL) {
        
    			return NULL;
    		}
    		tmp->adjvex = v2;
    		tmp->weight = w;
    		loc1 = LocateVertex(*A, v1);
    		tmp->nextarc = A->vertex[loc1].firstarc;
    		A->vertex[loc1].firstarc = tmp;
    	}
    	return A;
    }
    
    void FindID(AdjList A, int indegree[MAX_VER_NUM])
    {
           //求入度
    	ArcNode* tmp;
    	tmp = (ArcNode*)malloc(sizeof(ArcNode));
    	if (tmp == NULL) {
        
    		return;
    	}
    	for (int i = 0; i < A.num_vex; i++) {
        
    		indegree[i] = 0;
    	}
    	int loc;
    	for (int i = 0; i < A.num_vex; i++) {
        
    		tmp = A.vertex[i].firstarc;
    		while (tmp != NULL) {
        
    			loc = LocateVertex(A, tmp->adjvex);
    			indegree[loc]++;
    			tmp = tmp->nextarc;
    		}
    	}
    }
    
    int ve[MAX_VER_NUM];//每个顶点最早发生时间
    int TopoOrder(AdjList A, Stack *T)
    {
           //将最早时间填入ve数列中，将拓扑序列填入T栈中
    	int count = 0, loc1, loc2;
    	ArcNode *tmp;
    	int indegree[MAX_VER_NUM];
    	Stack S;
    	*T = InitStack();
    	S = InitStack();
    	FindID(A, indegree);
    	for (int i = 0; i < A.num_vex; i++) {
        
    		if (indegree[i] == 0) {
        
    			PushStack(&S, i);
    		}
    	}
    	for (int i = 0; i < A.num_vex; i++) {
        
    		ve[i] = 0;
    	}
    	while (S.top != -1) {
        
    		PopStack(&S, &loc1);
    		PushStack(T, loc1);
    		count++;
    		tmp = A.vertex[loc1].firstarc;
    		while (tmp != NULL) {
        
    			loc2 = tmp->adjvex;
    			indegree[loc2]--;
    			if (indegree[loc2] == 0) {
        
    				PushStack(&S, loc2);
    			}
    			if (ve[loc1] + tmp->weight > ve[loc2]) {
        
    				ve[loc2] = ve[loc1] + tmp->weight;
    			}
    			tmp = tmp->nextarc;
    		}
    	}
    	if (count < A.num_vex) {
        
    		return 0;
    	}
    	else return 1;
    }
    
    int CriticalPath(AdjList A)
    {
           //关键路径
    	ArcNode* tmp;
    	int loc1, loc2, v, tmp_w, ei, li;
    	char tag;
    	int vl[MAX_VER_NUM];//每个顶点最晚发生时间
    	Stack T;
    	if (!TopoOrder(A, &T)) {
        
    		//求事件最早发生时间和逆拓扑序列栈
    		return 0;
    	}
    	for (int i = 0; i < A.num_vex; i++) {
        
    		//将各顶点事件最迟发生时间初始化为汇点最早发生时间
    		vl[i] = ve[A.num_vex - 1];
    	}
    	while(T.top != -1) {
        
    		//按逆拓扑序列求各顶点vl值
    		PopStack(&T, &loc1);
    		tmp = A.vertex[loc1].firstarc;
    		while (tmp != NULL) {
        
    			v = tmp->adjvex;
    			tmp_w = tmp->weight;
    			loc2 = LocateVertex(A, v);
    			if (vl[loc2] - tmp_w < vl[loc1]) {
        
    				vl[loc1] = vl[loc2] - tmp_w;
    			}
    			tmp = tmp->nextarc;
    		}
    	}
    	printf("起始点\t终点\t权重\t最早时间 最晚时间 标志(带*为关键活动)\n");
    	for (int i = 0; i < A.num_vex; i++) {
        
    		//求ei、li和关键路径
    		tmp = A.vertex[i].firstarc;
    		while (tmp != NULL) {
        
    			v = tmp->adjvex;
    			loc2 = LocateVertex(A, v);
    			tmp_w = tmp->weight;
    			ei = ve[i];
    			li = vl[loc2] - tmp_w;
    			if (ei == li) {
        
    				tag = '*';
    			}
    			else tag = ' ';//标记并输出关键活动
    			printf("%d\t%d\t%d\t%d\t %d\t %c\n", A.vertex[i].data, A.vertex[loc2].data, tmp_w, ei, li, tag);
    			tmp = tmp->nextarc;
    		}
    	}
    	printf("\n最终耗时：\n");
    	printf("%d",ve[A.num_vex-1]);
    	return 1;
    }

运行截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221014/fb86618b67ea4ce58be88d07b6d3898e.png