跳到主要内容

图论基础

图论是计算机科学和数学中的一个重要分支，研究图（Graph）的结构和性质。图由节点（顶点）和边组成，用于表示对象之间的关系。图论在计算机网络、社交网络分析、路径规划等领域有广泛应用。

什么是图？​

图（Graph）是由一组顶点（Vertices）和一组边（Edges）组成的结构。顶点表示对象，边表示对象之间的关系。图可以分为有向图和无向图：

  • 无向图：边没有方向，表示双向关系。
  • 有向图：边有方向，表示单向关系。

图的表示方法​

图可以通过以下两种常见方式表示：

  1. 邻接矩阵：用二维数组表示图中顶点之间的连接关系。
  2. 邻接表：用链表或数组的数组表示每个顶点的邻居。

邻接矩阵示例​

假设有一个无向图，顶点为 A, B, C，边为 A-B 和 B-C，其邻接矩阵如下：

  A B C
A 0 1 0
B 1 0 1
C 0 1 0

邻接表示例​

同样的图用邻接表表示为：

A -> [B]
B -> [A, C]
C -> [B]

图的基本术语​

  • 顶点（Vertex）：图中的节点。
  • 边（Edge）：连接两个顶点的线。
  • 路径（Path）：从一个顶点到另一个顶点经过的边的序列。
  • 环（Cycle）：起点和终点相同的路径。
  • 度（Degree）：无向图中与顶点相连的边的数量。有向图中分为入度和出度。

图的遍历​

图的遍历是访问图中所有顶点的过程。常见的遍历方法有：

  1. 深度优先搜索（DFS）：从一个顶点出发，沿着一条路径尽可能深入，直到无法继续为止，然后回溯。
  2. 广度优先搜索（BFS）：从一个顶点出发，逐层访问其邻居。

DFS 示例代码​

以下是用 Python 实现的 DFS 算法：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')

输出：

A
B
D
E
F
C

BFS 示例代码​

以下是用 Python 实现的 BFS 算法：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)

# 示例图
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

bfs(graph, 'A')

输出：

A
B
C
D
E
F

实际应用场景​

  1. 社交网络分析：用图表示用户之间的关系，分析社区结构或信息传播路径。
  2. 路径规划：在地图应用中，用图表示地点和道路，寻找最短路径。
  3. 推荐系统：用图表示用户和物品之间的关系，推荐相关物品。

总结​

图论是计算机科学中一个强大且实用的工具。通过学习图的基本概念、表示方法和遍历算法，你可以解决许多实际问题。接下来，你可以尝试实现更复杂的图算法，如最短路径算法（Dijkstra）或最小生成树算法（Kruskal）。

附加资源与练习​

  • 练习 1：实现一个无向图的邻接表表示，并编写 DFS 和 BFS 算法。
  • 练习 2：尝试用图表示你所在城市的地铁线路，并找到两个站点之间的最短路径。
  • 推荐资源：
    • 《算法导论》中的图论章节
    • LeetCode 上的图论题目
提示

学习图论时，动手实践非常重要！尝试自己实现算法并解决实际问题。