注释如下：
class DirectedGraph {
private:
int numVertices; // 图中顶点的数量
vector<vector<pair<int, int>>> adjacencyList; // 邻接表，存储每个顶点的出边和对应的权重
public:
DirectedGraph(int n) : numVertices(n), adjacencyList(n) {} // 构造函数，初始化图的顶点数量和邻接表大小
void addEdge(int u, int v, int weight) {
adjacencyList[u].push_back(make_pair(v, weight)); // 添加一条从顶点u到顶点v的有向边，并设置权重为weight
}
vector<int> topologicalSort() {
vector<int> inDegree(numVertices, 0); // 记录每个顶点的入度
for (int u = 0; u < numVertices; ++u) { // 遍历所有顶点
for (auto& edge : adjacencyList[u]) { // 遍历当前顶点u的出边
int v = edge.first; // 出边连接的顶点v
++inDegree[v]; // 递增顶点v的入度
}
}
queue<int> q;
for (int u = 0; u < numVertices; ++u) {
if (inDegree[u] == 0) { // 将入度为0的顶点入队列
q.push(u);
}
}
vector<int> sortedOrder;
while (!q.empty()) {
int u = q.front();
q.pop();
sortedOrder.push_back(u); // 将当前顶点加入排序结果
for (auto& edge : adjacencyList[u]) { // 遍历当前顶点的出边
int v = edge.first; // 出边连接的顶点v
--inDegree[v]; // 递减顶点v的入度
if (inDegree[v] == 0) { // 如果顶点v的入度变为0，将其入队列
q.push(v);
}
}
}
return sortedOrder; // 返回拓扑排序结果
}
void findCriticalPath() {
vector<int> inDegree(numVertices, 0); // 记录每个顶点的入度
for (int u = 0; u < numVertices; ++u) { // 遍历所有顶点
for (auto& edge : adjacencyList[u]) { // 遍历当前顶点u的出边
int v = edge.first; // 出边连接的顶点v
++inDegree[v]; // 递增顶点v的入度
}
}
vector<int> startTime(numVertices, 0);
vector<int> endTime(numVertices, 0);
queue<int> q;
for (int u = 0; u < numVertices; ++u) {
if (inDegree[u] == 0) { // 将入度为0的顶点入队列
q.push(u);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& edge : adjacencyList[u]) { // 遍历当前顶点的出边
int v = edge.first; // 出边连接的顶点v
int weight = edge.second; // 边的权重
inDegree[v]--;
startTime[v] = max(startTime[v], startTime[u] + weight); // 计算顶点v的开始时间
if (inDegree[v] == 0) { // 如果顶点v的入度变为0，将其入队列
q.push(v);
}
}
endTime[u] = startTime[u]; // 设置当前顶点u的结束时间等于开始时间（只有一个路径）
}
int criticalPathLength = *max_element(endTime.begin(), endTime.end()); // 找到关键路径长度
cout << "Critical path length: " << criticalPathLength << endl;
cout << "Critical path nodes: ";
int currentNode = -1;
for (int i = 0; i < numVertices; ++i) {
if (endTime[i] == criticalPathLength && currentNode == -1) {
currentNode = i;
cout << currentNode << " "; // 输出关键路径上的第一个节点
}
else if (endTime[i] == criticalPathLength && startTime[i] == startTime[currentNode]) {
currentNode = i;
cout << currentNode << " "; // 输出和第一个节点具有相同开始时间的其他节点
}
}
cout << endl;
}
};
以上是一个使用邻接表实现有向图的C++类，包含了添加边、拓扑排序和寻找关键路径等功能。
内容由零声教学AI助手提供，问题来源于学员提问
