用c语言写输出关键路径 功能描述:根据创建的有向图及权重,调用TopologicalSort函数应用栈结构输出关键路径。 输出格式printf("Criticalpath: <%d,%d> length: %d\n", 开始节点数组index下标, 下一节点数组index下标, 权重); 例如: Criticalpath: <0,2> length: 4 Criticalpath: <2,3> length: 8 Criticalpath: <3,4> length: 4 Critic
时间: 2024-02-22 12:57:00 浏览: 64
c语言实现 关键路径
5星 · 资源好评率100%
好的,你的问题是如何用C语言编写输出关键路径的功能,我会为你解答。
首先,我们需要用到之前定义的AOE网结构体和栈结构体:
```
typedef struct {
int data[MAX_VERTEX_NUM];
int top;
} Stack;
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
int weight; // 权值
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点的数据
int indegree; // 顶点的入度
int top_num; // 顶点的拓扑序号
int ee; // 事件最早发生时间
int el; // 事件最迟发生时间
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;
typedef struct {
VNode vertices[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和弧数
} ALGraph;
```
接下来,我们需要实现关键路径算法,具体步骤如下:
1. 对AOE网进行拓扑排序,计算每个顶点的事件最早发生时间ee。
2. 对AOE网进行逆拓扑排序,计算每个顶点的事件最迟发生时间el。
3. 遍历每条弧,找到关键路径,输出关键路径的开始节点、下一节点和权重。
具体的代码实现如下:
```
void CriticalPath(ALGraph *G) {
int i, j, k;
int ee, el, maxe = 0;
Stack S;
ArcNode *p;
// 初始化栈S
S.top = -1;
// 拓扑排序,计算ee
TopologicalSort(G, &S);
for (i = 0; i < G->vexnum; i++) {
G->vertices[i].ee = 0;
}
while (S.top != -1) {
i = Pop(&S);
for (p = G->vertices[i].firstarc; p != NULL; p = p->next) {
j = p->adjvex;
if (G->vertices[i].ee + p->weight > G->vertices[j].ee) {
G->vertices[j].ee = G->vertices[i].ee + p->weight;
}
}
}
// 逆拓扑排序,计算el
for (i = 0; i < G->vexnum; i++) {
G->vertices[i].el = G->vertices[G->vexnum-1].ee;
}
for (k = G->vexnum-2; k >= 0; k--) {
i = G->vertices[k].top_num;
for (p = G->vertices[i].firstarc; p != NULL; p = p->next) {
j = p->adjvex;
if (G->vertices[j].el - p->weight < G->vertices[i].el) {
G->vertices[i].el = G->vertices[j].el - p->weight;
}
}
}
// 输出关键路径
for (i = 0; i < G->vexnum; i++) {
for (p = G->vertices[i].firstarc; p != NULL; p = p->next) {
j = p->adjvex;
ee = G->vertices[i].ee;
el = G->vertices[j].el - p->weight;
if (ee == el) {
printf("Criticalpath: <%d,%d> length: %d\n", i, j, p->weight);
if (p->weight > maxe) {
maxe = p->weight;
}
}
}
}
printf("Criticalpath length: %d\n", maxe);
}
```
这样,我们就完成了输出关键路径的功能。你可以根据自己的需要进行修改和扩展。
阅读全文