图论基础知识
什么是图论?
图论(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):按层次逐层访问顶点。
-
最短路径算法:
-
最小生成树:
-
拓扑排序:
- 对有向无环图(DAG)进行排序,使得每条边的起点在终点之前。
-
连通性检测:
- Tarjan算法:用于检测强连通分量。
- 并查集(Union-Find):检测无向图的连通性。
应用场景
- 网络结构:如社交网络分析、通信网络建模。
- 路径规划:如导航系统中的最短路径计算。
- 资源分配:如任务调度、流水线作业优化。
- 数据结构设计:如依赖关系分析、图数据库。