图的遍历与最短路径算法

# 1. 理解图的基本概念

## 1.1 图的基本定义

在计算机科学中，图是由节点（顶点）和边组成的一种数据结构。图可以用来表示各种实际问题中的关系，比如社交网络中的好友关系、城市之间的道路网络等。图的基本定义包括以下几个要点：

- 节点（Vertex）：也称为顶点，是图中的基本元素，用来表示实体。
- 边（Edge）：连接节点的线段，用来表示节点之间的关系。边可以是有向的（箭头表示方向）、无向的（双向）、带权重的等。
- 度（Degree）：节点的度是指与该节点相连的边的数量。
- 路径（Path）：一系列顶点，顶点之间相邻且有边连接。
- 连通图（Connected Graph）：图中的任意两个顶点之间都存在路径。
- 子图（Subgraph）：一个图的子集，包括一部分顶点和一部分边。
- ...

## 1.2 图的分类与特性

根据图的性质和特点，可以将图分为多种类型，常见的包括：

- 有向图（Directed Graph）：边有方向的图。
- 无向图（Undirected Graph）：边没有方向的图。
- 加权图（Weighted Graph）：边具有权重（或距离）的图。
- 有向无环图（Directed Acyclic Graph, DAG）：有向图中不存在环路的图。
- 连通图（Connected Graph）：任意两点之间都存在路径的图。
- 强连通图（Strongly Connected Graph）：有向图中任意两个节点都相互可达的图。
- ...

图的特性包括连通性、强连通性、图的生成树（Spanning Tree）、图的度分布等。

## 1.3 图的表示方法

图可以通过多种方法来进行表示，常见的有：

- 邻接矩阵（Adjacency Matrix）：使用二维数组表示节点之间的连接关系。
- 邻接表（Adjacency List）：使用链表或数组表示每个节点的相邻节点。
- 关联矩阵（Incidence Matrix）：使用二维数组表示节点和边的关系。
- ...

这些表示方法各自适用于不同的场景，选择合适的表示方法可以有效地进行图的存储和操作。

# 2. 图的遍历算法

在图论中，遍历算法是一种用于访问图中所有顶点的常见算法。通过遍历算法，我们可以在图中搜索特定的节点或路径，也可以检测图中的环路等信息。

### 深度优先搜索（DFS）算法

深度优先搜索是一种用于遍历或搜索树或图的算法。它从起始顶点开始，沿着路径一直向前直到不能继续为止，然后返回到最近的尚未搜索过的节点继续遍历，直到图中所有节点都被访问过。在实现DFS时，通常使用栈（Stack）数据结构来保存遍历路径。

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

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

print("DFS traversal order:")
dfs(graph, 'A')

**代码说明：**
- `dfs` 函数实现了深度优先搜索算法，使用集合 `visited` 记录已经访问过的节点。
- 示例代码中给出了一个图的表示和遍历方法。运行代码将输出深度优先搜索的遍历顺序。

### 广度优先搜索（BFS）算法

广度优先搜索是另一种图的遍历算法，它从起始顶点开始，先访问起始顶点的所有邻接节点，然后再逐层向下继续访问。在实现BFS时，通常使用队列（Queue）数据结构来保存遍历路径。

from collections import deque

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