图论基础知识
什么是图论？
图论（Graph Theory）是研究图（Graph）的数学分支，主要研究点和边之间的关系。在计算机科学、网络设计、生物信息学等领域中，图论有广泛的应用。
图的基本定义
-
图 (Graph)
一个图 ( G = (V, E) ) 由以下两部分组成：- ( V )：顶点集合（Vertices），表示对象。
- ( E )：边集合（Edges），表示顶点之间的关系。
-
边的类型：
- 无向边：顶点之间的关系是对称的。
- 有向边：顶点之间的关系有方向性（例如箭头 ( u \rightarrow v )）。
- 加权边：每条边附带一个权值，表示强度或成本。
-
图的分类：
- 无向图：所有边都是无方向的。
- 有向图：所有边都有方向。
- 简单图：没有平行边和自环的图。
- 完全图：任意两个顶点之间都有一条边。
- 稀疏图：边的数量远小于顶点对的数量。
- 稠密图：边的数量接近顶点对的数量。
图的基本术语
-
度 (Degree)：
- 顶点的度是与其相连的边的数目。
- 无向图中，顶点的度为其连接的边数。
- 有向图中：
- 入度（In-degree）：指向该顶点的边数。
- 出度（Out-degree）：从该顶点出发的边数。
-
路径 (Path)：
- 一系列顶点的序列，其中每一对相邻顶点之间都有边。
- 简单路径：路径中没有重复的顶点。
-
回路 (Cycle)：
- 从一个顶点出发，通过若干边返回该顶点的路径。
- 无重复顶点（除起点和终点）。
-
连通性 (Connectivity)：
- 无向图：如果任意两个顶点之间都有路径，则为连通图。
- 有向图：如果任意两个顶点之间都有双向路径，则为强连通图。
-
子图 (Subgraph)：
- 从图中选取一部分顶点和边构成的图。
图的表示方式
-
邻接矩阵 (Adjacency Matrix)：
用一个 ( n * n ) 的矩阵表示图，其中 ( A[i][j] ) 表示顶点 ( i ) 和 ( j ) 之间是否有边。
优点：快速查询边的存在性。
缺点：空间复杂度高，特别是对稀疏图。示例：
0 1 0 1 0 1 0 1 0 -
邻接表 (Adjacency List)：
用一个列表表示每个顶点的邻接顶点。
优点：空间高效，适合稀疏图。
缺点：查询特定边的存在性较慢。示例：
0: [1] 1: [0, 2] 2: [1]
常见算法
-
图遍历：
- 深度优先搜索（DFS）：递归地访问每个未访问的相邻顶点。
- 广度优先搜索（BFS）：按层次逐层访问顶点。
-
最短路径算法：
- Dijkstra算法：适用于加权图，不能处理负权边。
- Bellman-Ford算法：适用于处理负权边。
- Floyd-Warshall算法：计算所有点对之间的最短路径。
-
最小生成树：
- Prim算法：从一个顶点开始，逐步构建生成树。
- Kruskal算法：按权值排序边，然后逐步添加到生成树中。
-
拓扑排序：
- 对有向无环图（DAG）进行排序，使得每条边的起点在终点之前。
-
连通性检测：
- Tarjan算法：用于检测强连通分量。
- 并查集（Union-Find）：检测无向图的连通性。
应用场景
- 网络结构：如社交网络分析、通信网络建模。
- 路径规划：如导航系统中的最短路径计算。
- 资源分配：如任务调度、流水线作业优化。
- 数据结构设计：如依赖关系分析、图数据库。
