图论基础知识

什么是图论？

图论（Graph Theory）是研究图（Graph）的数学分支，主要研究点和边之间的关系。在计算机科学、网络设计、生物信息学等领域中，图论有广泛的应用。

图的基本定义

1. 图 (Graph)
   一个图 ( G = (V, E) ) 由以下两部分组成：

   • ( V )：顶点集合（Vertices），表示对象。
   • ( E )：边集合（Edges），表示顶点之间的关系。

2. 边的类型：

   • 无向边：顶点之间的关系是对称的。
   • 有向边：顶点之间的关系有方向性（例如箭头 ( u \rightarrow v )）。
   • 加权边：每条边附带一个权值，表示强度或成本。

3. 图的分类：

   • 无向图：所有边都是无方向的。
   • 有向图：所有边都有方向。
   • 简单图：没有平行边和自环的图。
   • 完全图：任意两个顶点之间都有一条边。
   • 稀疏图：边的数量远小于顶点对的数量。
   • 稠密图：边的数量接近顶点对的数量。

图的基本术语

1. 度 (Degree)：

   • 顶点的度是与其相连的边的数目。
   • 无向图中，顶点的度为其连接的边数。
   • 有向图中：
     • 入度（In-degree）：指向该顶点的边数。
     • 出度（Out-degree）：从该顶点出发的边数。

2. 路径 (Path)：

   • 一系列顶点的序列，其中每一对相邻顶点之间都有边。
   • 简单路径：路径中没有重复的顶点。

3. 回路 (Cycle)：

   • 从一个顶点出发，通过若干边返回该顶点的路径。
   • 无重复顶点（除起点和终点）。

4. 连通性 (Connectivity)：

   • 无向图：如果任意两个顶点之间都有路径，则为连通图。
   • 有向图：如果任意两个顶点之间都有双向路径，则为强连通图。

5. 子图 (Subgraph)：

   • 从图中选取一部分顶点和边构成的图。

图的表示方式

1. 邻接矩阵 (Adjacency Matrix)：
   用一个 ( n * n ) 的矩阵表示图，其中 ( A[i][j] ) 表示顶点 ( i ) 和 ( j ) 之间是否有边。
   优点：快速查询边的存在性。
   缺点：空间复杂度高，特别是对稀疏图。

   示例：

   0 1 0
   1 0 1
   0 1 0
   

   • 1
   • 2
   • 3

2. 邻接表 (Adjacency List)：
   用一个列表表示每个顶点的邻接顶点。
   优点：空间高效，适合稀疏图。
   缺点：查询特定边的存在性较慢。

   示例：

   0: [1]
   1: [0, 2]
   2: [1]
   

   • 1
   • 2
   • 3

常见算法

1. 图遍历：

   • 深度优先搜索（DFS）：递归地访问每个未访问的相邻顶点。
   • 广度优先搜索（BFS）：按层次逐层访问顶点。

2. 最短路径算法：

   • Dijkstra算法：适用于加权图，不能处理负权边。
   • Bellman-Ford算法：适用于处理负权边。
   • Floyd-Warshall算法：计算所有点对之间的最短路径。

3. 最小生成树：

   • Prim算法：从一个顶点开始，逐步构建生成树。
   • Kruskal算法：按权值排序边，然后逐步添加到生成树中。

4. 拓扑排序：

   • 对有向无环图（DAG）进行排序，使得每条边的起点在终点之前。

5. 连通性检测：

   • Tarjan算法：用于检测强连通分量。
   • 并查集（Union-Find）：检测无向图的连通性。

应用场景

1. 网络结构：如社交网络分析、通信网络建模。
2. 路径规划：如导航系统中的最短路径计算。
3. 资源分配：如任务调度、流水线作业优化。
4. 数据结构设计：如依赖关系分析、图数据库。