无向图

一、无向图的基本概念

1. 定义：
   • 无向图由一组顶点（vertex）和一组连接两个顶点的边（edge）组成。
   • 边没有方向，记为 v-w 或 w-v，表示顶点 v 和 w 之间的无向连接。
2. 表示方法：
   • 顶点通常用 0 到 V-1 的整数表示（V 为顶点总数），便于数组索引操作。
   • 可用符号表将顶点名映射到整数索引。
3. 特殊情况：
   • 自环：连接顶点自身的边。
   • 平行边：连接同一对顶点的多条边。
   • 简单图：无自环和平行边的图。
   • 多重图：允许平行边的图。

二、术语表

1. 相邻顶点：通过一条边连接的两个顶点。
2. 度数：依附于某顶点的边总数。
3. 子图：由图的部分边及其依附顶点构成的图。
4. 路径：
   • 一系列顶点通过边顺序连接。
   • 简单路径：无重复顶点的路径。
   • 长度：路径包含的边数。
5. 环：
   • 起点和终点相同的路径，至少含一条边。
   • 简单环：除起点和终点外，无重复顶点和边的环。
6. 连通性：
   • 若两顶点间存在路径，则称两顶点连通。
   • 连通图：任意顶点间都有路径。
   • 连通分量：图中极大连通子图。
7. 无环图：不含环的图。
8. 树：
   • 无环连通图。
   • 生成树：包含图中所有顶点的树形子图。
   • 森林：互不相连的树的集合。
9. 图的密度：
   • 已连接顶点对占所有可能的顶点对比例。
   • 稀疏图：边数较少（E ≈ 小常数 × V）。
   • 稠密图：边数接近最大可能值。
10. 二分图：
    • 可将顶点分为两部分，每条边连接的顶点分属不同部分的图。

三、树的性质

• 一幅含 V 个顶点的图是树，当且仅当满足以下任一条件：
  1. 有 V-1 条边且无环。
  2. 有 V-1 条边且连通。
  3. 连通，但删除任一条边会断开连通性。
  4. 无环，但添加任一条边会产生环。
  5. 任意顶点对间只有一条简单路径。

四、图的表示方法

1. 邻接矩阵：
   • V × V 布尔矩阵，[v][w] = true 表示 v-w 有边。
   • 空间复杂度：V²，不适合稀疏图。
2. 边的数组：
   • 用类 Edge 存储每条边的两个顶点。
   • 空间复杂度：E，但查询邻接顶点需遍历所有边，效率低。
3. 邻接表（推荐）：
   • 以顶点为索引的数组，每个元素是一个链表，存储该顶点的邻接顶点。
   • 空间复杂度：V + E。
   • 添加边时间：常数。
   • 遍历邻接顶点时间：与度数成正比。

五、图处理算法

1. 深度优先搜索（DFS）：
   • 思想：从起点递归访问未标记的邻接顶点，标记已访问顶点。
   • 时间复杂度：V + E（与顶点度数之和成正比）。
   • 应用：
     • 单点连通性：标记与起点连通的所有顶点。
     • 单点路径：用 edgeTo[] 记录路径，找到从起点到某顶点的路径。
     • 连通分量：识别图中所有连通子图。
     • 检测环：若访问已标记顶点且非父节点，则有环。
     • 双色问题：用两种颜色着色，判断是否为二分图。
2. 广度优先搜索（BFS）：
   • 思想：用队列从起点逐层访问邻接顶点，确保找到最短路径。
   • 时间复杂度：V + E。
   • 应用：
     • 单点最短路径：找到从起点到某顶点的最短路径。
   • 命题：BFS 保证找到的路径是最短的。

六、符号图

1. 定义：
   • 用字符串而非整数表示顶点名。
   • 输入格式：每行表示一组边，顶点名用分隔符隔开。
2. 实现：
   • 符号表 st：映射顶点名到索引。
   • 反向索引 keys[]：映射索引到顶点名。
   • 图对象 G：用索引表示图。
   • 构造需遍历输入文件两遍：第一遍建索引，第二遍建图。
3. 应用：
   • 间隔度数：如 Kevin Bacon 游戏，用 BFS 找最短路径。

七、算法性能总结

问题	实现方法	时间复杂度
单点连通性	DepthFirstSearch	V + E
单点路径	DepthFirstPaths	V + E
单点最短路径	BreadthFirstPaths	V + E
连通分量	CC	V + E
检测环	Cycle	V + E
二分图检测	TwoColor	V + E