图论基础

图论基础

图论是数学和计算机科学中研究图的结构与性质的学科，广泛应用于社交网络分析、路径规划、计算机网络等领域。本章将介绍图的基本概念、存储方式及基础算法。

基本概念

图的定义

一个图（Graph）由以下两部分组成：

• 顶点集（Vertices）：$V=\{v_1,v_2,...,v_n\}$
• 边集（Edges）：$E=\{e_1,e_2,...,e_m\}$，其中每条边连接两个顶点

图的分类

根据边的性质，图可分为：

• 无向图：边没有方向，用圆括号表示，如$(A,B)$
• 有向图：边有方向，用尖括号表示，如$⟨A,B⟩$
• 加权图：边带有权重值

graph LR A--无向边-->B C-->|有向边|D E--权重5---F

图的存储方式

邻接矩阵

用二维数组存储顶点间的连接关系，适合稠密图。

# 无向图的邻接矩阵示例
adj_matrix = [
    [0, 1, 1, 0],  # A连接B和C
    [1, 0, 0, 1],  # B连接A和D
    [1, 0, 0, 1],  # C连接A和D
    [0, 1, 1, 0]   # D连接B和C
]

邻接表

用链表存储每个顶点的邻居，适合稀疏图。

# 有向图的邻接表示例
adj_list = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

基础算法

深度优先搜索（DFS）

递归探索图的"深度"方向。

def dfs(graph, node, visited):
    if node not in visited:
        print(node)  # 处理节点
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# 示例调用
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A', set())

输出：

A
B
D
C

广度优先搜索（BFS）

按层次遍历图的节点。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)  # 处理节点
            visited.add(node)
            queue.extend(graph[node])

# 示例调用
bfs(graph, 'A')

输出：

A
B
C
D

实际应用案例

社交网络分析

在社交网络中：

• 顶点表示用户
• 边表示好友关系
• 使用BFS可以找到两用户之间的最短连接路径

路径规划

导航系统使用加权图：

• 顶点表示地点
• 边表示道路
• 权重表示距离或时间
• 常用Dijkstra算法找最短路径

复杂度分析

图算法复杂度比较

算法	时间复杂度	空间复杂度
DFS	$O(|V|+|E|)$	$O(|V|)$
BFS	$O(|V|+|E|)$	$O(|V|)$
邻接矩阵存储	$O(1)$查询	$O(|V{|}^2)$
邻接表存储	$O(degree(v))$查询	$O(|V|+|E|)$

练习建议

1. 实现图的三种存储方式 2. 分别用DFS和BFS遍历给定的图 3. 设计一个社交网络的好友推荐系统原型

通过掌握这些基础知识，您将为学习更高级的图算法（如最短路径、最小生成树等）打下坚实基础。