利用有向网的的邻接表存储结构实现关键路径算法

关键路径算法是一种常用的项目管理工具，可以帮助确定项目中最长的关键路径和关键活动。实现关键路径算法需要用到有向网的邻接表存储结构，具体步骤如下：

1. 定义有向网的邻接表存储结构，其中包含顶点表和边表两个部分。

2. 根据项目的具体情况，构建有向网的邻接表，包括顶点和边的信息。

3. 对有向网进行拓扑排序，得到所有顶点的拓扑序列。

4. 对拓扑序列中的每一个顶点，分别计算其最早开始时间和最晚开始时间，并记录其前驱和后继活动。

5. 根据前面的计算结果，计算每一个活动的最早开始时间和最晚开始时间，以及其总时差。

6. 找到所有关键活动，即总时差为0的活动，以及关键路径，即所有关键活动构成的路径。

7. 输出关键路径和关键活动的信息。

需要注意的是，实现关键路径算法需要对有向网进行拓扑排序，因此有向网必须是一个有向无环图。如果有向网中存在环路，则无法进行拓扑排序，也无法求解关键路径和关键活动。

相关问题

采用邻接表存储，实现关键路径算法代码和思路

关键路径算法是用于求解工程项目中最长的完成时间和关键活动的一种算法。邻接表是一种图的存储方式，可以用来存储有向无环图(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;
}

这段代码首先使用邻接表存储了所有的有向边，然后统计了每个节点的入度。接着使用拓扑排序的方法计算了每个节点的最早开始时间，最后计算了每个节点的最晚开始时间，并输出了关键路径上的节点。

需要注意的是，在计算每个节点的最晚开始时间时，需要从终点开始向起点遍历，因为只有先计算出终点的最晚开始时间，才能够计算出其他节点的最晚开始时间。

采用邻接表存储，实现关键路径算法具体代码

关键路径算法是一种用于确定项目完成所需时间的技术，其重点在于找出各个活动的最早开始时间、最晚开始时间、总时差和自由时差。在实现时采用邻接表存储有向无环图（DAG），具体代码如下：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.vertices = vertices
        self.indegree = [0] * vertices
        self.topo_order = []
        self.start_time = [0] * vertices
        self.end_time = [0] * vertices
        self.critical_path = []

    def add_edge(self, u, v, weight):
        self.graph[u].append((v, weight))
        self.indegree[v] += 1

    def get_indegree(self, v):
        return self.indegree[v]

    def get_topo_order(self):
        return self.topo_order

    def get_start_time(self, v):
        return self.start_time[v]

    def get_end_time(self, v):
        return self.end_time[v]

    def get_critical_path(self):
        return self.critical_path

    def topological_sort(self):
        queue = []
        for i in range(self.vertices):
            if self.indegree[i] == 0:
                queue.append(i)

        while queue:
            u = queue.pop(0)
            self.topo_order.append(u)

            for v, weight in self.graph[u]:
                self.indegree[v] -= 1
                if self.indegree[v] == 0:
                    queue.append(v)
                    self.start_time[v] = max(self.start_time[v], self.end_time[u])
                self.end_time[u] = max(self.end_time[u], self.start_time[u] + weight)

    def find_critical_path(self):
        for u in range(self.vertices):
            for v, weight in self.graph[u]:
                if self.start_time[u] + weight == self.start_time[v]:
                    self.critical_path.append((u, v, weight))

if __name__ == '__main__':
    g = Graph(7)
    g.add_edge(0, 1, 3)
    g.add_edge(0, 2, 2)
    g.add_edge(1, 3, 4)
    g.add_edge(2, 3, 2)
    g.add_edge(3, 4, 4)
    g.add_edge(3, 5, 3)
    g.add_edge(4, 6, 2)
    g.add_edge(5, 6, 1)

    g.topological_sort()
    g.find_critical_path()

    print("Topological order:", g.get_topo_order())
    print("Start time:", g.start_time)
    print("End time:", g.end_time)
    print("Critical path:", g.get_critical_path())

在上述代码中，我们首先定义了一个 Graph 类，其中包含邻接表、顶点数、每个顶点的入度、拓扑排序后的顺序、每个顶点的最早开始时间、最晚开始时间、关键路径等信息。然后定义了一些方法，包括添加边、获取入度、获取拓扑排序后的顺序、获取最早开始时间、最晚开始时间和关键路径等。其中，topological_sort() 方法实现了拓扑排序，find_critical_path() 方法实现了查找关键路径。

在主函数中，我们定义了一个 7 个顶点的 DAG，并添加了各个顶点之间的边。然后调用 topological_sort() 方法进行拓扑排序，再调用 find_critical_path() 方法查找关键路径。最后输出了拓扑排序后的顺序、每个顶点的最早开始时间、最晚开始时间和关键路径等信息。