python中的图

在 Python 中，图（Graph）是一个非常重要的数据结构，特别是在刷算法题时。图有许多类型（如有向图、无向图、有权图、无权图等），并且涉及的算法（如深度优先搜索、广度优先搜索、最短路径等）都非常常见。以下是 Python 中常见的图的语法，尤其是刷算法题时用到的技巧。

1. 图的基本定义

图通常由两部分组成：

• 顶点（节点）：图中的每个元素。
• 边（连接顶点的线）：连接两个顶点的关系。

Python 中表示图的方式有两种常见的方式：

• 邻接矩阵：使用一个二维数组来表示图。
• 邻接表：使用字典或列表来存储每个节点的相邻节点（边）。

1.1 邻接矩阵

邻接矩阵适用于存储密集图（边较多的图）。每个节点与其他节点之间的边存在于一个二维矩阵中，matrix[i][j] 为 1 表示有边从节点 i 到节点 j，为 0 则表示没有。

# 使用二维列表表示图
n = 5  # 图的顶点数量
graph = [[0] * n for _ in range(n)]

# 假设图是无向图，添加边 (0, 1) 和 (1, 2)
graph[0][1] = 1
graph[1][0] = 1
graph[1][2] = 1
graph[2][1] = 1

# 打印邻接矩阵
for row in graph:
    print(row)

1.2 邻接表

邻接表更适合稀疏图（边较少的图）。它使用一个字典或列表，键表示图的节点，值为该节点的所有相邻节点。

# 使用字典表示图
graph = {
    0: [1, 2],  # 0 节点与 1 和 2 相连
    1: [0, 2],  # 1 节点与 0 和 2 相连
    2: [0, 1],  # 2 节点与 0 和 1 相连
    3: [4],     # 3 节点与 4 相连
    4: [3]      # 4 节点与 3 相连
}

# 打印邻接表
for node, neighbors in graph.items():
    print(f"Node {node}: {neighbors}")

2. 图的遍历：深度优先搜索 (DFS) 和广度优先搜索 (BFS)

在图算法中，遍历是常见的操作。常用的图遍历算法有 深度优先搜索（DFS）和 广度优先搜索（BFS）。

2.1 深度优先搜索 (DFS)

深度优先搜索是从一个节点开始，尽可能深入地访问每一个节点，直到没有未访问的邻居节点。DFS 可以使用递归或栈来实现。

递归实现 DFS：

# 使用邻接表表示图
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
    3: [4],
    4: [3]
}

# 递归实现 DFS
def dfs(graph, node, visited):
    print(node, end=" ")
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

visited = set()
dfs(graph, 0, visited)  # 从节点 0 开始 DFS

非递归实现 DFS（使用栈）：

# 使用栈实现 DFS
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

dfs_iterative(graph, 0)  # 从节点 0 开始 DFS

2.2 广度优先搜索 (BFS)

广度优先搜索是从起始节点开始，依次访问离起始节点较近的节点，逐层扩展。BFS 通常使用队列来实现。

from collections import deque

# 使用队列实现 BFS
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

bfs(graph, 0)  # 从节点 0 开始 BFS

3. 常见图算法

3.1 最短路径算法

Dijkstra 算法（适用于有权图）：
Dijkstra 算法用于寻找从起点到所有其他节点的最短路径，适用于图中的边权为正的情况。

import heapq

def dijkstra(graph, start):
    # 初始化最短路径
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    priority_queue = [(0, start)]  # (distance, node)

    while priority_queue:
        d, node = heapq.heappop(priority_queue)

        if d > dist[node]:
            continue

        for neighbor, weight in graph[node]:
            distance = d + weight
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return dist

# 使用邻接表表示图，图中的每个边是 (邻居, 权重)
graph = {
    0: [(1, 4), (2, 1)],
    1: [(2, 2), (3, 5)],
    2: [(3, 1)],
    3: []
}

print(dijkstra(graph, 0))  # 从节点 0 开始计算最短路径

3.2 拓扑排序

拓扑排序用于有向无环图（DAG）。它可以找到一个节点的线性排列，使得每个节点的前驱节点都在其之前。

from collections import deque

def topological_sort(graph):
    # 计算每个节点的入度
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 将入度为 0 的节点加入队列
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []

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

# 使用邻接表表示图
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: []
}

print(topological_sort(graph))  # 输出拓扑排序结果

3.3 判断图是否是二分图

如果一个图是二分图，那么我们可以将图中的节点分成两部分，使得每条边都连接两部分中的一个节点。可以使用 BFS 来判断图是否是二分图。

from collections import deque

def isBipartite(graph):
    color = {}
    
    def bfs(start):
        queue = deque([start])
        color[start] = 0  # 给起始节点上色
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]  # 给邻居节点上相反的色
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:  # 如果邻居节点和当前节点同色，则不是二分图
                    return False
        return True
    
    for node in graph:
        if node not in color:
            if not bfs(node):
                return False
    
    return True

# 使用邻接表表示图
graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

print(isBipartite(graph))  # 输出是否是二分图

4. 总结：

• 图的表示： 使用邻接矩阵适用于密集图，使用邻接表适用于稀疏图。
• 图的遍历： 深度优先搜索（DFS）和

广度优先搜索（BFS）是图算法的基础。

• 常见算法： 最短路径（Dijkstra），拓扑排序，判断二分图等。
• 图的相关问题： 包括连通性、最短路径、环检测等问题。

这些是刷图类算法题时常用的语法和技巧，理解这些基础知识对解决更复杂的图问题至关重要。