aoe网求关键路径c语言代码
时间: 2023-12-11 15:32:04 浏览: 55
以下是求解AOE网关键路径的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 10
#define MAX_ARC_NUM 100
typedef struct ArcNode {
int adjvex;
int weight;
struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
int data;
ArcNode *firstarc;
} VNode;
typedef struct {
VNode vertices[MAX_VERTEX_NUM];
int vexnum, arcnum;
} AGraph;
int *etv, *ltv;
int *stack2;
int top2 = -1;
void CreateGraph(AGraph *G) {
int i, j, k, w;
ArcNode *p;
printf("请输入顶点数和弧数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入%d个顶点:", G->vexnum);
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入%d条弧的起点、终点和权值:\n", G->arcnum);
for (k = 0; k < G->arcnum; k++) {
scanf("%d%d%d", &i, &j, &w);
p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = w;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
}
}
void TopologicalSort(AGraph *G) {
int i, k, gettop;
int top = -1;
int *stack;
stack = (int *) malloc(G->vexnum * sizeof(int));
for (i = 0; i < G->vexnum; i++) {
if (G->vertices[i].firstarc == NULL) {
stack[++top] = i;
}
}
top2 = -1;
etv = (int *) malloc(G->vexnum * sizeof(int));
for (i = 0; i < G->vexnum; i++) {
etv[i] = 0;
}
stack2 = (int *) malloc(G->vexnum * sizeof(int));
while (top != -1) {
gettop = stack[top--];
stack2[++top2] = gettop;
for (ArcNode *p = G->vertices[gettop].firstarc; p != NULL; p = p->nextarc) {
k = p->adjvex;
if (--indegree[k] == 0) {
stack[++top] = k;
}
if (etv[gettop] + p->weight > etv[k]) {
etv[k] = etv[gettop] + p->weight;
}
}
}
if (top2 != G->vexnum - 1) {
printf("该AOE网存在环,无法进行拓扑排序!\n");
exit(0);
}
}
void CriticalPath(AGraph *G) {
int i, j, k;
int ete, lte;
ArcNode *p;
TopologicalSort(G);
ltv = (int *) malloc(G->vexnum * sizeof(int));
for (i = 0; i < G->vexnum; i++) {
ltv[i] = etv[G->vexnum - 1];
}
while (top2 != -1) {
gettop = stack2[top2--];
for (p = G->vertices[gettop].firstarc; p != NULL; p = p->nextarc) {
k = p->adjvex;
if (ltv[k] - p->weight < ltv[gettop]) {
ltv[gettop] = ltv[k] - p->weight;
}
}
}
for (j = 0; j < G->vexnum; j++) {
for (p = G->vertices[j].firstarc; p != NULL; p = p->nextarc) {
k = p->adjvex;
ete = etv[j];
lte = ltv[k] - p->weight;
if (ete == lte) {
printf("<%d, %d> length: %d, ", j, k, p->weight);
}
}
}
}
int main() {
AGraph *G;
G = (AGraph *) malloc(sizeof(AGraph));
CreateGraph(G);
CriticalPath(G);
return 0;
}
```