图示例

# @ignore-function-tree
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()
    queue = [{'node': start, 'distance': 0}]
    
    while queue:
        # 找到当前距离最小的节点
        current = min(queue, key=lambda x: x['distance'])
        queue.remove(current)
        current_node = current['node']
        
        if current_node in visited:
            continue
        visited.add(current_node)
        
        # 更新邻居节点的距离
        for neighbor, weight in graph[current_node].items():
            new_distance = distances[current_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                queue.append({'node': neighbor, 'distance': new_distance})
    
    return distances

graph = create_graph({
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
})

shortest_distances = dijkstra(graph, 'A')

def bfs(graph, start):
    visited = set()
    queue = Queue()
    queue.enqueue(start)
    visited.add(start)
    result = []
    
    while queue.size:
        node = queue.dequeue()
        result.append(node)
        # 遍历当前节点的所有邻居
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)
    return result

graph = create_graph({
    '1': {'2': 3, '3': 5},
    '2': {'1': 3, '4': 2, '5': 6},
    '3': {'1': 5, '5': 4},
    '4': {'2': 2, '5': 1, '6': 3},
    '5': {'2': 6, '3': 4, '4': 1},
    '6': {'4': 3}
})
bfs(graph, '1')

def dfs(graph, start):
    visited = set()
    stack = Stack()
    stack.push(start)
    visited.add(start)
    result = []
    
    while stack.size:
        node = stack.pop()
        result.append(node)
        # 遍历当前节点的所有邻居
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.push(neighbor)
    return result

# 示例图的定义
graph = create_graph({
    'Core': {'A': 5, 'B': 3, 'C': 7},
    'A': {'Core': 5},
    'B': {'Core': 3, 'D': 2},
    'C': {'Core': 7},
    'D': {'B': 2}
})

dfs(graph, 'A')

def bellman_ford(graph, start):
    # 初始化距离字典
    distance = {node: float('infinity') for node in graph}
    distance[start] = 0

    # 松弛操作：遍历所有边 V-1 次
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distance[node] + weight < distance[neighbor]:
                    distance[neighbor] = distance[node] + weight

    # 检测负权环：如果还能松弛，则存在负权环
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distance[node] + weight < distance[neighbor]:
                return "图中存在负权环！"

    return distance

# 示例图（包含负权边）
graph = create_graph({
    'A': {'B': 4, 'C': 5},
    'B': {'C': -2, 'D': 3},
    'C': {'D': 4},
    'D': {'E': 2},
    'E': {}
})

# 从节点 'A' 计算最短路径
result = bellman_ford(graph, 'A')

def kahn_algorithm(graph):
    # 初始化入度字典
    in_degree = {node: 0 for node in graph}
    # 计算所有节点的入度
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 初始化队列，将所有入度为0的节点加入队列
    queue = Queue()
    for node in in_degree:
        if in_degree[node] == 0:
            queue.enqueue(node)
    topological_order = []
    
    # 处理队列中的节点
    while queue.size:
        current_node = queue.dequeue()
        topological_order.append(current_node)
        # 遍历当前节点的所有邻居，减少它们的入度
        for neighbor in graph[current_node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.enqueue(neighbor)
    
    # 检查是否存在环
    if len(topological_order) != len(graph):
        return "图中存在环！无法生成拓扑排序。"
    else:
        return topological_order

# 示例图（课程依赖关系）
graph = create_graph({
    '数据结构': ['算法'],
    '算法': ['机器学习'],
    '数学': ['机器学习', '深度学习'],
    '机器学习': ['深度学习'],
    '深度学习': [],
    'Python基础': ['数据结构', '数学']
}, True)

# 执行Kahn算法
result = kahn_algorithm(graph)