9 非线性数据结构之图

在前一篇，我们深入探讨了非线性数据结构中的树，理解了其基本概念、性质和应用。本篇将继续探索非线性数据结构，但将重点转向图。图是一种更为复杂且灵活的数据结构，广泛应用于各种领域，如社交网络、交通网络和推荐系统等。接下来，我们将详细介绍图的基本概念、表示方法、基本操作及应用场景。

图的基本概念

图是由节点（或称为“顶点”）和连接节点的边构成的数据结构。我们通常用符号 $G=(V, E)$ 来表示图，其中：

• $V$ 是图中的顶点集合。
• $E$ 是图中的边集合，每条边是一个顶点对。

图的分类

根据边的性质，图可以分为以下几类：

1. 无向图：边没有方向，表示两个顶点之间的双向关系。例如，社交网络中的朋友关系。
2. 有向图：边有方向，表示一个顶点指向另一个顶点的关系。例如，网页之间的超链接。
3. 加权图：每条边都有一个权重（权值），通常表示距离、费用等。例如，地图上的路程。
4. 无权图：边不带权重，通常认为所有边的权重相同。

图的表示方法

图的表示通常有两种主要方式：邻接矩阵和邻接表。

邻接矩阵

邻接矩阵是一种二维数组，用于表示图中的边。对于一个有 $n$ 个顶点的图，邻接矩阵是一个 $n \times n$ 的矩阵，其中 $matrix[i][j]$ 的值表示顶点 $i$ 和顶点 $j$ 之间是否有边相连（在加权图中则表示边的权重）。

示例：

对于一个有向图如下：

A → B
A → C
B → D
C → D

其邻接矩阵为：

    A B C D
A [ 0 1 1 0 ]
B [ 0 0 0 1 ]
C [ 0 0 0 1 ]
D [ 0 0 0 0 ]

邻接表

邻接表是一种更节省空间的图表示方式。它为每个顶点维护一个链表，链表中存储与该顶点相邻的所有顶点。

示例：

对于同样的有向图，其邻接表表示为：

A: B → C
B: D
C: D
D: 

代码实现

以下是使用 Python 实现邻接表的示例代码：

class Graph:
    def __init__(self):
        self.graph = {}
    
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def display(self):
        for vertex in self.graph:
            print(f"{vertex}: {' -> '.join(self.graph[vertex])}")

# 创建图的实例
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")

g.display()

图的基本操作

图常见的基本操作包括：

1. 添加顶点：在图中添加一个新的顶点。
2. 添加边：在两个顶点之间添加一条边。
3. 删除顶点：从图中删除一个顶点及其相关的边。
4. 删除边：从图中删除一条边。

图的遍历

图的遍历有两种主要方法：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索是一种使用递归或栈实现的遍历方法。它会尽可能深入到每一个分支的子节点直到不可再深入。

DFS 示例代码：

def dfs(graph, vertex, visited):
    if vertex not in visited:
        print(vertex, end=' ')
        visited.add(vertex)
        for neighbor in graph.get(vertex, []):
            dfs(graph, neighbor, visited)

# 执行 DFS
visited = set()
print("DFS Traversal:")
dfs(g.graph, "A", visited)

广度优先搜索（BFS）

广度优先搜索是一种使用队列实现的遍历方法。它会首先访问一层的所有节点，然后再访问下一层的节点。

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, end=' ')
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)

# 执行 BFS
print("\nBFS Traversal:")
bfs(g.graph, "A")

图的应用场景

图在现实世界中有广泛的应用：

• 社交网络：表示用户及其关系。
• 地图导航：表示城市及其路网，便于路径规划。
• 网络流量分析：监测数据流动和分析网络效率。
• 推荐系统：研究用户之间的关系与偏好。

总结

本篇文章介绍了非线性数据结构中的图，涵盖了基本概念、表示方法、基本操作及其遍历。图以其灵活性和表现力，成为许多复杂问题建模的重要工具。接下来，我们将继续讨论另一种非线性数据结构：堆。希望您能在此基础上进一步探索图的深奥与美妙！