Python高级数据结构：图、树和堆的应用，解决复杂数据处理问题

# 1. Python高级数据结构概述**

Python高级数据结构是用于存储、组织和处理复杂数据的强大工具。它们超越了基本数据类型（如列表和元组），提供了更高级的组织和操作功能。这些数据结构包括图、树、堆等，它们在解决现实世界问题中发挥着至关重要的作用。

高级数据结构的优势在于它们能有效地处理复杂关系、层次结构和优先级。它们允许数据以结构化和高效的方式存储，从而简化数据处理任务。例如，图结构可以表示社交网络中的关系，而树结构可以表示文件系统中的目录层次。

# 2. 图结构的应用

### 2.1 图论基础知识

图是一种数据结构，用于表示对象之间的关系。它由一组节点（顶点）和一组边组成，其中边连接两个节点。图可以用来表示各种各样的关系，例如社交网络中的朋友关系、道路网络中的道路连接关系，或计算机网络中的计算机连接关系。

### 2.2 图的表示和遍历算法

#### 2.2.1 邻接矩阵

邻接矩阵是一个二维数组，其中每个元素表示两个节点之间的边权重。如果两个节点之间没有边，则相应的元素为 0。邻接矩阵表示法简单易用，但对于稀疏图（边数远少于节点数）来说，空间效率较低。

# 创建一个邻接矩阵
adj_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [0, 0, 1, 0]
]

#### 2.2.2 邻接表

邻接表是一种使用链表表示图的表示法。每个节点都有一个链表，其中包含与该节点相连的所有边的信息。邻接表表示法对于稀疏图来说空间效率更高，但对于稠密图（边数接近或超过节点数）来说，查找边的时间复杂度更高。

# 创建一个邻接表
adj_list = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2]
}

#### 2.2.3 深度优先搜索

深度优先搜索（DFS）是一种遍历图的算法，它沿着一条路径深入搜索，直到无法再继续深入为止，然后再回溯并继续搜索其他路径。DFS 算法可以用来查找图中的环、连通分量和生成树。

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

#### 2.2.4 广度优先搜索

广度优先搜索（BFS）是一种遍历图的算法，它从一个起始节点开始，并逐层遍历与该节点相邻的所有节点，然后再遍历与这些节点相邻的所有节点，以此类推。BFS 算法可以用来查找图中的最短路径和最短生成树。

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(n