图的表示方法
邻接矩阵
V乘V的布尔矩阵,v和w之间有连接的边时,定义v行w列的元素值为true。
问题:不适合含有大量顶点的图。不能表示平行边。
边的数组
使用一个Edge类,含有两个int实例。
问题:实现adj()需要检查图中所有的边。
邻接表数组
以顶点为索引,每个元素都是和该定点相邻的顶点列表。
邻接表添加边
为了添加一条连接v与w的边,将w添加到v的邻接表中,并且把v添加到w的邻接表中。
性能
- 空间和V+E成正比
- 所需时间为常数
- 遍历顶点v的所有相邻顶点所需时间和v的度数成正比
搜索
深度优先搜索
伪码
1 | //Recursive |
解决问题
- 连通性:判断两个顶点是否连通,或图中有多少个连通子图。
- 单点路径:给定一幅图和一个起点s,判断从s到给定顶点v是否存在一条路径。
DFS记录路径
可以添加一个edgeTo[]数组,在由边v-w第一次访问w时,将edgeTo[w]设为v来记住这条路径。也就是v-w是从起点s到w的最后一条已知的边。当最后需要取得路径时,可以通过将edgeTo压栈取得。

广度优先搜索
伪码
1 | Breadth-First-Search(Graph, root): |
解决问题
单点最短路径
BFS查找路径

搜索的一般步骤
在搜索中我们都会先将起点存入数据结构,然后重复以下步骤直到数据结构被清空:
- 取其中的下一个顶点并标记它。
- 将v的所有相邻而又未被标记的顶点加入数据结构。
回溯(Backtracking)
回溯可以枚举出部分(或)全部问题的解,而不是一个解。
一般一个解被当作潜在搜索树(potential search tree)的一个节点。每个节点的子节点是该节点经过单步拓展所得,树的叶子节点是不能再被拓展的解。
回溯算法递归地搜索该树,按照深度优先的顺序。
伪码
- root(P): return the partial candidate at the root of the search tree.
- reject(P,c): return true only if the partial candidate c is not worth completing.
- accept(P,c): return true if c is a solution of P, and false otherwise.
- first(P,c): generate the first extension of candidate c.
- next(P,s): generate the next alternative extension of a candidate, after the extension s.
- output(P,c): use the solution c of P, as appropriate to the application.
1 | procedure bt(c) |
有时候s ← first(P,c)和s ← next(P,s)可以合并写入到那个while循环中。
回溯练习
深刻理解上面的理论后,去leetcode找了几道medium难度的回溯问题。分别是:
17-Letter Combinations of a Phone Number
1 | //17-Letter Combinations of a Phone Number |
131-Palindrome Partitioning
1 | /131-Palindrome Partitioning |
216-Combination Sum III
1 | //216-Combination Sum III |