CS61B 课程笔记（Lecture 27 Graphs)

1. 图的定义

图的基本组成：
- 一组节点（或称为顶点）。
- 一组零个或多个边，每条边连接两个节点。
图的特点：
- 任何结构都是一个有效的图。
- 所有的树都是图，但并不是所有的图都是树。

2. 图的类型

简单图与多重图

简单图（Simple Graph）：
- 每对节点之间最多有一条边，且不允许有自环（即边连接节点自身）。
多重图（Multigraph）：
- 允许节点之间有多条边，可能存在自环。

其他图的分类

无向图（Undirected Graph）：
- 边的连接是双向的，例如边 (u, v) 意味着从节点 u 到节点 v 以及从节点 v 到节点 u。
有向图（Directed Graph）：
- 边的连接是单向的，例如边 (u, v) 意味着从节点 u 到节点 v，而反向不一定存在。
无环图（Acyclic Graph）：
- 图中不存在任何循环（从一个节点出发，经过若干边又回到该节点）。
循环图（Cyclic Graph）：
- 存在从某个节点出发，经过一些边再回到起始节点的路径。

3. 图的问题

常见的图问题：
- s-t路径（s-t Path）： 是否存在从节点 s 到节点 t 的路径？
- 连通性（Connectivity）： 图是否是连通的，是否存在任意两个节点之间的路径？
- 双连通性（Biconnectivity）： 是否存在一个节点的移除会使图不再连通？
- 最短 s-t 路径（Shortest s-t Path）： 节点 s 和节点 t 之间的最短路径是什么？
- 循环检测（Cycle Detection）： 图中是否存在循环？
- 欧拉巡游（Euler Tour）： 是否存在一个循环使用每条边一次且仅一次？
- 哈密顿巡游（Hamilton Tour）： 是否存在一个循环经过每个节点一次且仅一次？
- 可绘制性（Planarity）： 能否在纸上绘制图形而不交叉边？
- 同构性（Isomorphism）： 两个图是否同构（即是相同的图但以不同的形式表示）？
问题复杂性：
- 并不是所有图的问题都有清晰的复杂性界限，例如欧拉巡游问题是一个已解决的问题，而哈密顿巡游问题至今仍未找到有效解法，已知的最佳算法时间复杂度是指数级的。

4. 深度优先搜索

问题描述： 给定一个源节点 s 和一个目标节点 t，判断是否存在从 s 到 t 的路径。

初步尝试的代码：

if (s == t):
    return true;

for child in neighbors(s):
    if isconnected(child, t):
        return true;

return false;

问题： 上述代码会导致无限循环。

改进方法： 使用“记住已访问节点”的方法：

mark s  // 记住已经访问过 s
if (s == t):
    return true;

for child in unmarked_neighbors(s): // 忽略已标记的邻居
    if isconnected(child, t):
        return true;

return false;