图论基础：图的表示与遍历算法

# 1. 图论基础

## 1.1 图的介绍

图是一种抽象的数学模型，由若干个节点（顶点）以及连接这些节点的边组成。图可以用来表示各种事物之间的关系，如社交网络中的好友关系、交通网络中的路线等。

## 1.2 图的分类

根据图中边的性质，图可以分为有向图和无向图。有向图中的边有方向性，表示顶点之间的单向关系；无向图中的边没有方向性，表示顶点之间的双向关系。

## 1.3 图的重要性

图在计算机科学中有着广泛的应用，例如用于表示网络拓扑、路径规划、推荐系统等。理解图论基础对于深入学习图算法具有重要意义。

# 2. 图的表示

**2.1 邻接矩阵表示法**

在图论中，图的邻接矩阵表示法是一种常用的图表示方法。邻接矩阵是一个二维数组，用于表示图中的顶点之间的连接关系。邻接矩阵的大小为n×n，其中n表示图的顶点数量。在邻接矩阵中，如果两个顶点之间有边连接，则对应位置的元素为1；如果两个顶点之间没有边连接，则对应位置的元素为0。

以下是使用Python语言实现邻接矩阵表示法的代码示例：

# 定义图的邻接矩阵表示法类
class AdjacencyMatrixGraph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    # 添加边
    def add_edge(self, v1, v2):
        self.matrix[v1][v2] = 1
        self.matrix[v2][v1] = 1

    # 打印邻接矩阵
    def print_graph(self):
        for row in self.matrix:
            print(row)

# 创建一个包含5个顶点的图
graph = AdjacencyMatrixGraph(5)

# 添加边
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

# 打印邻接矩阵
graph.print_graph()

代码解析：
1. 定义了一个`AdjacencyMatrixGraph`类，用于实现邻接矩阵图。
2. `__init__`方法用于初始化图的顶点数量和邻接矩阵。
3. `add_edge`方法用于添加边，将对应位置的元素置为1。
4. `print_graph`方法用于打印邻接矩阵。

运行以上代码，输出结果为：

[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]

**2.2 邻接表表示法**

邻接表表示法是另一种常用的图表示方法。相比于邻接矩阵，邻接表更加节省空间，适用于稀疏图（边数量较少）的情况。邻接表使用链表的方式存储每个顶点的邻接顶点。

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

# 定义图的邻接表表示法类
class AdjacencyListGraph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.graph = [[] for _ in range(num_vertices)]

    # 添加边
    def add_edge(self, v1, v2):
        self.graph[v1].append(v2)
        self.graph[v2].append(v1)

    # 打印邻接表
    def print_graph(self):
        for vertex in range(self.num_vertices):
            print("顶点", vertex)
            for neighbor in self.graph[vertex]:
                print(" ->", neighbor)

# 创建一个包含5个顶点的图
graph = AdjacencyListGraph(5)

# 添加边
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

# 打印邻接表
graph.print_graph()

代码解析：
1. 定义了一个`AdjacencyListGraph`类，用于实现邻接表图。
2. `__init__`方法用于初始化图的顶点数量和邻接表。
3. `add_edge`方法用于添加边，将顶点v2加入到顶点v1的邻接表中，并将顶点v1加入到顶点v2的邻接表中。
4. `print_graph`方法用于打印邻接表。

运行以上代码，输出结果为：

顶点 0
 -> 1
 -> 4
顶点 1
 -> 0
 -> 2
 -> 3
 -> 4
顶点 2
 -> 1
 -> 3
顶点 3
 -> 1
 -> 2
 -> 4
顶点 4
 -> 0
 -> 1
 -> 3

# 3. 图的遍历算法

图的遍历算法是指对图中的节点进行遍历的方法。常见的图的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。下面将详细介绍这两种算法的原理和实现。

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

深度优先搜索是一种使用栈（Stack）数据结构来实现的图遍历算法。它的基本思想是从起始节点开始，沿着一条路径一直向下遍历，直到无法继续下去，然后回退到前一个节点继续遍历其他路径。具体步骤如下：

1.