队列实现关键路径算法代码
时间: 2024-03-18 08:37:42 浏览: 14
队列是一种常用的数据结构,用于实现关键路径算法时可以辅助进行拓扑排序。下面是一个使用队列实现关键路径算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
int weight; // 弧的权值
struct ArcNode* nextarc; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode* firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum; // 顶点数
int arcnum; // 弧数
} ALGraph;
// 初始化有向图
void InitGraph(ALGraph* G, int vexnum, int arcnum) {
G->vexnum = vexnum;
G->arcnum = arcnum;
for (int i = 0; i < vexnum; i++) {
G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
}
// 添加有向边
void AddArc(ALGraph* G, int start, int end, int weight) {
ArcNode* arc = (ArcNode*)malloc(sizeof(ArcNode));
arc->adjvex = end;
arc->weight = weight;
arc->nextarc = G->vertices[start].firstarc;
G->vertices[start].firstarc = arc;
}
// 拓扑排序
void TopologicalSort(ALGraph* G, int* ve) {
int indegree[MAX_VERTEX_NUM] = {0}; // 记录每个顶点的入度
int queue[MAX_VERTEX_NUM]; // 队列
int front = 0, rear = 0; // 队列的头尾指针
// 统计每个顶点的入度
for (int i = 0; i < G->vexnum; i++) {
ArcNode* arc = G->vertices[i].firstarc;
while (arc != NULL) {
indegree[arc->adjvex]++;
arc = arc->nextarc;
}
}
// 将入度为0的顶点入队
for (int i = 0; i < G->vexnum; i++) {
if (indegree[i] == 0) {
queue[rear++] = i;
}
}
while (front != rear) {
int v = queue[front++]; // 出队一个顶点
ArcNode* arc = G->vertices[v].firstarc;
while (arc != NULL) {
int w = arc->adjvex;
if (--indegree[w] == 0) {
queue[rear++] = w; // 入度为0的顶点入队
}
if (ve[v] + arc->weight > ve[w]) {
ve[w] = ve[v] + arc->weight; // 更新最早开始时间
}
arc = arc->nextarc;
}
}
}
// 关键路径算法
void CriticalPath(ALGraph* G) {
int ve[MAX_VERTEX_NUM] = {0}; // 最早开始时间
int vl[MAX_VERTEX_NUM] = {0}; // 最晚开始时间
int e[MAX_VERTEX_NUM] = {0}; // 事件最早发生时间
int l[MAX_VERTEX_NUM] = {0}; // 事件最晚发生时间
TopologicalSort(G, ve); // 拓扑排序,计算最早开始时间
// 计算最晚开始时间
for (int i = G->vexnum - 1; i >= 0; i--) {
int v = i;
ArcNode* arc = G->vertices[v].firstarc;
while (arc != NULL) {
int w = arc->adjvex;
if (vl[w] - arc->weight < vl[v] || vl[v] == 0) {
vl[v] = vl[w] - arc->weight; // 更新最晚开始时间
}
arc = arc->nextarc;
}
}
// 计算关键路径
for (int i = 0; i < G->vexnum; i++) {
int v = i;
ArcNode* arc = G->vertices[v].firstarc;
while (arc != NULL) {
int w = arc->adjvex;
int ete = ve[v]; // 事件最早发生时间
int ltl = vl[w] - arc->weight; // 事件最晚发生时间
if (ete == ltl) {
printf("%d -> %d\n", v, w); // 输出关键路径上的边
}
arc = arc->nextarc;
}
}
}
int main() {
ALGraph G;
int vexnum = 6; // 顶点数
int arcnum = 8; // 弧数
InitGraph(&G, vexnum, arcnum);
// 添加有向边
AddArc(&G, 0, 1, 3);
AddArc(&G, 0, 2, 2);
AddArc(&G, 1, 3, 4);
AddArc(&G, 1, 4, 3);
AddArc(&G, 2, 3, 2);
AddArc(&G, 2, 4, 1);
AddArc(&G, 3, 5, 2);
AddArc(&G, 4, 5, 3);
CriticalPath(&G); // 计算关键路径
return 0;
}
```
这段代码实现了关键路径算法,使用了邻接表来表示有向图。其中,`InitGraph`函数用于初始化有向图,`AddArc`函数用于添加有向边,`TopologicalSort`函数用于进行拓扑排序,`CriticalPath`函数用于计算关键路径。
关键路径算法的基本思想是通过拓扑排序计算每个顶点的最早开始时间,然后再计算每个顶点的最晚开始时间,最后根据最早开始时间和最晚开始时间的关系确定关键路径。