queue<int> q; for (int i = 0; i < nodes.size(); ++i) { if (nodes[i].successors.empty()) { q.push(i); latestFinish[i] = nodes[i].earliestStart; } } while (!q.empty()) { int curr = q.front(); q.pop(); for (int predecessor : nodes[curr].predecessors) { if (latestFinish[predecessor] == -1) { q.push(predecessor); latestFinish[predecessor] = latestFinish[curr] - nodes[predecessor].duration; } else { latestFinish[predecessor] = min(latestFinish[predecessor], latestFinish[curr] - nodes[predecessor].duration); } } } } void calculateCriticalPath() { for (int i = 0; i < nodes.size(); ++i) { if (nodes[i].earliestStart == latestFinish[i]) { cout << "Node " << nodes[i].id << " is on the critical path." << endl; } } }解释上述代码

上述代码是一个计算关键路径的算法。关键路径是指在一个项目中，所有任务都按最短时间完成的路径。

首先，代码定义了一个队列 q，用于存储没有后继任务的节点。

然后，通过遍历 nodes 数组，找到没有后继任务的节点，并将其添加到队列 q 中，并将该节点的最晚完成时间（latestFinish）设置为其最早开始时间（earliestStart）。

接下来，使用 while 循环从队列 q 中取出节点进行处理。对于每个取出的节点 curr，遍历其所有前驱节点 predecessor。

如果前驱节点的最晚完成时间尚未计算（即等于 -1），则将其添加到队列 q 中，并将其最晚完成时间设置为当前节点的最晚完成时间减去前驱节点的执行时间。

如果前驱节点的最晚完成时间已经计算过（即不等于 -1），则将其最晚完成时间更新为当前节点的最晚完成时间减去前驱节点的执行时间和原最晚完成时间的较小值。

最后，通过 calculateCriticalPath 函数，遍历所有节点，并判断是否在关键路径上。如果一个节点的最早开始时间等于其最晚完成时间，则该节点是关键路径上的节点。

对于关键路径上的节点，代码会输出其编号及其在关键路径上的信息。

相关问题

void bfs3(int start) { bool visited[MAXN] = { false }; queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int node = q.front(); q.pop(); cout << nodes[node] << " "; for (int i = 0; i < adjacencyList[node].size(); i++) { int neighbor = adjacencyList[node][i]; if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } }将代码改成 实现深度优先搜索遍历，并输出所有遍历节点

void dfs(int node, bool visited[]) {
visited[node] = true;
cout << nodes[node] << " ";
for (int i = 0; i < adjacencyList[node].size(); i++) {
int neighbor = adjacencyList[node][i];
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}

void dfsTraversal(int start) {
bool visited[MAXN] = { false };
dfs(start, visited);
}

这是深度优先搜索的实现，使用递归函数进行遍历。在访问一个节点时，将该节点标记为已访问，并输出该节点。然后对该节点的所有未访问邻居节点进行递归遍历。

vector<int> eventualSafeNodes(vector<vector<int>> &graph)

graph) {
int n = graph.size();
vector<int> indegrees(n, 0); // indegrees[i] stores the indegree of node i
vector<vector<int>> adjList(n, vector<int>()); // adjList[i] stores the nodes that have an edge from i
queue<int> q; // queue for BFS

// Build adjacency list and indegrees
for (int i = 0; i < n; i++) {
for (int j : graph[i]) {
adjList[i].push_back(j);
indegrees[j]++;
}
}

// Add nodes with indegree 0 to the queue
for (int i = 0; i < n; i++) {
if (indegrees[i] == 0) {
q.push(i);
}
}

// BFS
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int next : adjList[curr]) {
indegrees[next]--;
if (indegrees[next] == 0) {
q.push(next);
}
}
}

// Add nodes with indegree 0 to the result
vector<int> res;
for (int i = 0; i < n; i++) {
if (indegrees[i] == 0) {
res.push_back(i);
}
}

return res;
}