mirror of
https://github.com/happyflyer/wangdao-data-structure.git
synced 2026-02-02 18:20:02 +08:00
2.9 KiB
2.9 KiB
图
1. 基本概念
图 G 是由顶点集 V 和边集 E 组成，记为：
G=(V,E)
其中，
V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）的集合。
\left \vert V \right \vert 表示图 G 中顶点的个数，也称图 G 的阶。
\left \vert E \right \vert 表示图 G 中边的条数。
V=\{A,B,C,D,E\},\left \vert V \right \vert=5
E=\{(A,B),(A,C),(A,E),(B,C),(C,D),(C,E)\},\left \vert E \right \vert=6
线性表、树都可以为空，但图不能为空。
- 无向图 & 有向图
- 简单图 & 多重图
- 完全图
- 子图
- 连通 & 强连通
- 连通图 & 强连通图
- 连通分量 & 强连通分量
- 极小连通子图
- 生成树、生成森林
- 顶点的度
- 网
- 稠密图 & 稀疏图
- 有向树
- 路径
- 路径长度
- 回路