图论术语
一句话简介
图论基础术语详解：图的结构组成、度的概念、边节点数量关系、子图类型及连通性等核心概念。
关键要点
1. 图的基本结构
- 节点 (Vertex)：图的基本组成单元，每个节点有唯一 ID
- 边 (Edge)：连接节点的线，可以是有向或无向
- 有向图 (Directed Graph)：边有方向，只能沿箭头方向到达
- 无向图 (Undirected Graph)：边无方向，可双向到达（可理解为双向图）
- 加权图 (Weighted Graph)：边带权重，可用于表示距离、成本等
- 无权图 (Unweighted Graph)：边无权重
2. 度的概念
- 度 (Degree)：无向图中与节点相连的边的条数
- 入度 (Indegree)：有向图中指向该节点的边数
- 出度 (Outdegree)：有向图中从该节点指向其他节点的边数
3. 边和节点的数量关系
- 简单图 (Simple Graph)：无自环边和多重边的图
- 边数的取值范围：$0 \leq E \leq V(V-1)/2 \approx V^2$
- 稠密图 (Dense Graph)：$E$ 接近 $V^2$，几乎每两个节点间都有边
- 稀疏图 (Sparse Graph)：$E$ 远小于 $V^2$，边很少
4. 子图
- 子图 (Subgraph)：从原图中删除一些节点和边后得到的图
- 生成子图 (Spanning Subgraph)：包含原图所有节点，但只包含部分边
- 导出子图 (Induced Subgraph)：选择部分节点 + 这些节点在原图中的所有边
5. 连通性
无向图：
- 连通图 (Connected Graph)：任意两个节点间都存在路径
- 连通分量 (Connected Component)：非连通图中的连通子图，一个图可有多个连通分量
有向图：
- 强连通图 (Strongly Connected Graph)：任意两节点间都存在有向路径
- 弱连通图 (Weakly Connected Graph)：忽略边方向后变成连通图
- 强连通分量 (SCC)：有向图中最大的强连通子图
- 弱连通分量 (WCC)：忽略方向后的连通分量
应用场景
- 地图 App：边权重表示距离
- 物流网络：边权重表示运输成本
- 最短路径算法、最小生成树算法等都基于这些基础概念
相关概念
- 图：由节点和边构成的数据结构
- 有向图：边有方向的图
- 无向图：边无方向的图
- 加权图：边带权重的图
- 节点：图的基本组成单元
- 边：连接节点的线
- 度：节点相连的边数
- 入度：有向图中指向节点的边数
- 出度：有向图中从节点指出的边数
- 简单图：无自环和多重边的图
- 稠密图：边数接近 $V^2$ 的图
- 稀疏图：边数远小于 $V^2$ 的图
- 子图：原图的子集
- 生成子图：包含所有节点的子图
- 导出子图：包含选定节点及其所有边的子图
- 连通图：任意两节点间有路径的图
- 连通分量：极大的连通子图
- 强连通图：有向图中任意两节点互相可达
- 弱连通图：忽略方向后连通的有向图
- 强连通分量：极大的强连通子图
- 弱连通分量：忽略方向后的连通分量
相关实体
- labuladong：算法学习平台作者