用数据结构完成图的深度优先和广度优先搜索图，还有求图的关键路径

好的，我会分别介绍用数据结构完成图的深度优先和广度优先搜索，以及求图的关键路径。

1. 深度优先搜索（DFS）：

深度优先搜索是一种遍历图的算法，它的基本思想是从一个起始节点开始，沿着一条边走到底，直到走到不能再走为止，然后退回到上一个节点，继续沿着其他的边走下去。这个过程不断重复，直到所有节点都被访问过。

深度优先搜索可以用递归或栈来实现。以下是使用栈实现的深度优先搜索代码：

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node] - visited)

    return visited

2. 广度优先搜索（BFS）：

广度优先搜索是一种遍历图的算法，它的基本思想是从一个起始节点开始，先访问所有与该节点直接相邻的节点，然后依次访问它们的相邻节点，直到所有节点都被访问过。

广度优先搜索可以用队列来实现。以下是使用队列实现的广度优先搜索代码：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node] - visited)

    return visited

3. 求图的关键路径：

关键路径是指在一个有向无环图中，从起点到终点的所有路径中，最长的那条路径。求图的关键路径可以使用拓扑排序和动态规划来实现。

以下是使用拓扑排序实现的求图的关键路径代码：

def topsort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = [node for node in graph if in_degree[node] == 0]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result

def critical_path(graph, duration):
    topo = topsort(graph)
    earliest = {node: 0 for node in topo}
    for node in topo:
        for neighbor in graph[node]:
            earliest[neighbor] = max(earliest[neighbor], earliest[node] + duration[node])

    latest = {node: earliest[node] for node in topo}
    latest[topo[-1]] = earliest[topo[-1]]
    for node in reversed(topo):
        for neighbor in graph[node]:
            latest[node] = min(latest[node], latest[neighbor] - duration[node])

    slack = {node: latest[node] - earliest[node] for node in topo}
    critical = {node for node in topo if slack[node] == 0}

    return earliest, latest, slack, critical

其中，`graph`是一个字典，表示有向无环图，`duration`是一个字典，表示每个节点的持续时间。`topsort`函数使用拓扑排序算法来排序节点，`critical_path`函数使用动态规划算法来计算关键路径。