图数据结构：图的表示、遍历与应用

# 1. 图的基本概念和表示**

图是一种数据结构，用于表示实体（称为顶点）之间的关系（称为边）。它广泛应用于各种领域，如社交网络分析、路径规划和数据挖掘。

**1.1 图的基本概念**

* **顶点（Vertex）：**图中的基本单元，表示实体或对象。
* **边（Edge）：**连接两个顶点的线段，表示实体之间的关系。边可以是有向的（有方向）或无向的（无方向）。
* **权重（Weight）：**与边关联的值，表示关系的强度或成本。

**1.2 图的表示**

图可以通过邻接矩阵或邻接表来表示。

* **邻接矩阵：**一个二维数组，其中元素表示顶点之间的权重。如果顶点之间没有边，则元素为无穷大。
* **邻接表：**一个数组，其中每个元素是一个链表，存储与该顶点相连的所有边的信息。

# 2. 图的遍历算法

图的遍历算法是用来访问图中所有顶点和边的系统方法。它在图的各种应用中发挥着至关重要的作用，例如路径查找、连通性检查和图的表示。

### 2.1 深度优先搜索（DFS）

#### 2.1.1 基本原理和实现

深度优先搜索（DFS）是一种遍历图的递归算法，它沿着从根节点开始的一条路径深入搜索，直到无法再进一步为止，然后回溯并探索其他分支。DFS的实现通常使用栈数据结构，它按照后进先出的原则存储顶点。

**算法步骤：**

1. 将根节点压入栈中。
2. 只要栈不为空，就弹出栈顶元素并访问它。
3. 将栈顶元素的所有未访问的相邻节点压入栈中。
4. 重复步骤2和3，直到栈为空。

**代码块：**

def dfs(graph, start):
    """
    深度优先搜索算法

    :param graph: 图的邻接表表示
    :param start: 起始节点
    """
    stack = [start]
    visited = set()

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

**逻辑分析：**

* `visited`集合用于跟踪已访问的节点，以避免重复访问。
* `stack`栈存储要访问的节点，后进先出。
* 算法从`start`节点开始，并不断访问其未访问的相邻节点，直到栈为空。

#### 2.1.2 应用场景

DFS适用于以下场景：

* 查找图中的环
* 检测图的连通性
* 拓扑排序

### 2.2 广度优先搜索（BFS）

#### 2.2.1 基本原理和实现

广度优先搜索（BFS）是一种遍历图的层序算法，它从根节点开始，逐层访问所有相邻节点，然后再访问下一层。BFS通常使用队列数据结构，它按照先进先出的原则存储顶点。

**算法步骤：**

1. 将根节点压入队列中。
2. 只要队列不为空，就弹出队列首元素并访问它。
3. 将队列首元素的所有未访问的相邻节点压入队列中。
4. 重复步骤2和3，直到队列为空。

**代码块：**

def bfs(graph, start):
    """
    广度优先搜索算法

    :param graph: 图的邻接表表示
    :param start: 起始节点
    """
    queue = [start]
    visited = set()

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

**逻辑分析：**

* `visited`集合用于跟踪已访问的节点，以避免重复访问。
* `queue`队列存储要访问的节点，先进先出。
* 算法从`start`节点开始，并不断访问其未访问的相邻节点，直到队列为空。

#### 2.2.2 应用场景

BFS适用于以下场景：

* 查找图中的最短路径
* 检测图的连通性
* 拓扑排序

# 3. 图的应用

### 3.1 最短路径算法

#### 3.1.1 Dijkstra算法

**基本原理：**

Dijkstra算法是一种贪心算法，用于求解从单一源点到所有其他顶点的最短路径。该算法通过迭代地选择当前已知最短路径距离最小的顶点，并更新其相邻顶点的最短路径距离来进行。

**实现：**

def dijkstra(graph, source):
    # 初始化距离和已访问标记
    distances = {vertex: float('infinity') for vertex in graph}
    visited = set()

    # 设置源点距离为 0
    distances[source] = 0

    # 循环，直到所有顶点都被访问
    while visited != set(graph):
        # 找出未访问顶点中距离最小的顶点
        current = min(set(graph) - visited, key=lambda vertex: distances[vertex])

        # 将当前顶点标记为已访问
        visited.add(current)

        # 更新相邻顶点的距离
        for neighbor in graph[current]:
            new_distance = distances[current] + graph[current][neighbor]
            if new_distance < distances[neighbor]:
                distances[n