采用邻接表存储,实现关键路径算法代码和思路
时间: 2023-12-10 17:40:56 浏览: 106
关键路径算法是用于求解工程项目中最长的完成时间和关键活动的一种算法。邻接表是一种图的存储方式,可以用来存储有向无环图(DAG),因此可以使用邻接表存储有向无环图来实现关键路径算法。
邻接表的基本思想是将图中每个点的出边存储到一个链表中,每个链表节点存储一个有向边的信息,包括该边的终点和权值。对于有向无环图中的每个节点,我们可以维护两个数组,一个存储该节点的入度,另一个存储该节点的最早开始时间。通过遍历整个图,我们可以计算出每个节点的最早开始时间和最晚开始时间,从而得到关键路径。
下面是使用邻接表存储有向无环图的伪代码:
```
struct EdgeNode {
int to; // 有向边的终点
int weight; // 有向边权值
int next; // 指向下一个节点的指针
};
EdgeNode edge[MAX_EDGE_NUM]; // 存储所有的有向边
int head[MAX_NODE_NUM]; // 存储每个节点的第一条出边的位置
int inDegree[MAX_NODE_NUM]; // 存储每个节点的入度
int earliestTime[MAX_NODE_NUM]; // 存储每个节点的最早开始时间
int latestTime[MAX_NODE_NUM]; // 存储每个节点的最晚开始时间
void addEdge(int from, int to, int weight) {
edge[edgeCnt].to = to;
edge[edgeCnt].weight = weight;
edge[edgeCnt].next = head[from];
head[from] = edgeCnt++;
}
void topologicalSort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i); // 将所有入度为0的节点加入队列
earliestTime[i] = 0; // 起点的最早开始时间为0
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].weight;
inDegree[v]--;
earliestTime[v] = max(earliestTime[v], earliestTime[u] + w);
if (inDegree[v] == 0) {
q.push(v);
}
}
}
}
void calcLatestTime() {
latestTime[n] = earliestTime[n]; // 终点的最晚开始时间等于最早开始时间
for (int u = n - 1; u >= 1; u--) {
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].weight;
latestTime[u] = min(latestTime[u], latestTime[v] - w);
}
}
}
void printCriticalPath() {
for (int i = 1; i <= n; i++) {
if (earliestTime[i] == latestTime[i]) { // 找到关键路径上的节点
printf("%d ", i);
}
}
printf("\n");
}
int main() {
memset(head, -1, sizeof(head));
memset(inDegree, 0, sizeof(inDegree));
memset(earliestTime, 0, sizeof(earliestTime));
memset(latestTime, INT_MAX, sizeof(latestTime));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w); // 添加一条有向边
inDegree[v]++; // 统计每个节点的入度
}
topologicalSort(); // 计算每个节点的最早开始时间
calcLatestTime(); // 计算每个节点的最晚开始时间
printCriticalPath(); // 输出关键路径上的节点
return 0;
}
```
这段代码首先使用邻接表存储了所有的有向边,然后统计了每个节点的入度。接着使用拓扑排序的方法计算了每个节点的最早开始时间,最后计算了每个节点的最晚开始时间,并输出了关键路径上的节点。
需要注意的是,在计算每个节点的最晚开始时间时,需要从终点开始向起点遍历,因为只有先计算出终点的最晚开始时间,才能够计算出其他节点的最晚开始时间。
阅读全文