算法第一遍看真的是只能面上过过, 难度还是挺高的, 不过至少原理懂了一些. 前边的排序和散列表除了红黑树删除那部分之外, 其他的倒也能懂, 问题不大.
图算法之前接触的很少, 现在来试着了解一下吧.
顶点与边
一个无向图, 就是一组顶点与边组成的图. 一般指代顶点用0-V-1来指代有V个顶点的图. 依据之前的数据结构, 有了符号表之后, 可以建立起任意的映射.
对于一个边来说, 可以用两个一组的顶点来表示一个边, 比如 v-w 表示v和w之间的边, 这个边与 w-v 是同一条边.
将图画出来可能会有助于理解, 但不要被画出来的图形所误导, 图的形状有很多种, 这里讨论的是无序图, 所以结构其实有很多种.
图里有两种特殊情况, 一种是一个边连接一个点和其自身, 这个叫做自环; 另外一种是两个点有多个边相连, 叫做平行边. 算法这本书还算入门, 不会讨论这两种情况.
知道了顶点和边之后, 还有一系列术语需要掌握:
- 相邻, 指两个顶点有边相连, 称这两个顶点是相邻的
- 依附, 一条边依附于其连接的两个顶点
- 度数, 指一个依附于一个顶点的边的数量
- 子图, 指一个图所有边的子集加上依附的顶点构成的图
- 路径, 由边顺序连接的一系列顶点
- 简单路径, 没有重复顶点的路径
- 环, 至少含有一条边且起点和重终点相同的路径
- 简单环, 除了起点=终点之外, 没有任何重复的顶点和边
- 长度, 路径或者环包含的边的数量
- 连通, 两个顶点之间存在一条路径, 可以使用 u-v-w-x 之类来表示
- 连通图, 任意一个顶点都存在路径到达其他所有顶点, 就是连通图. 一个非连通图由若干连通的部分组成, 这些连通的部分都是非连通图的极大连通子图
- 无环图, 不包含环的图. 树就是一种无环连通图, 互不相连的树组成的集合叫做森林. 一个连通图可以找到一个对应的生成树(也是这个连通图的子图), 这个生成树包含这个连通图的所有顶点, 但是没有环. 这种生成树不只一种, 其集合叫做生成树森林.
- 密度, 已经连接的顶点对, 占所有可能连接的顶点对总数的百分比. 百分比低的叫做稀疏图, 百分比高的叫做稠密图.
- 二分图, 每两个相连的顶点, 都属于不同类型的集合. 像一个三角形的环, 就无法成为一个二分图.
如何判断一个有V个结点的图G是一个树的方法已经研究的很成熟了, 有如下五个条件, 满足其中一个就是树:
- G有V-1条边且没有环
- G有V-1条边且连通
- G是连通的, 删掉任意一条边, 都不再连通
- G是无环图, 但添加任意一条边都会产生一条环
- G中任意一对顶点之间仅存在一条简单路径
这个几个东西都被数学证明了, 不过脑子里想一下, 还是挺直观的.
这一上来就一堆术语, 看来这图算法真的不太简单啊.
图的常用API
用哪种数据结构来表示图, 这是一个关键问题. 为此先来看一下一般图操作的API:
public class Graph
Graph(int V) //创建含有V个顶点但不含有边的图
Graph(In in) //从in读入图数据
int V() //获取顶点数
int E() //获取边数
void addEdge(int v, int w) //为v和w添加一个边
Iterable<Integer> adj(int v) //返回和V相邻的所有顶点
String toString() //将图打印为字符串
然后是依据这些API的一些方法:
- 计算顶点v的度数: 遍历adj,返回其中的顶点数
- 计算所有顶点的最大度数, 遍历各个顶点的度数然后返回其中的max值
- 计算顶点的平均度数, 直接用总边数除以总顶点数, 也就是使用E()/V()即可
- 计算自环的个数, 遍历所有顶点, 找到每个顶点的adj()返回结果中与自己相等的顶点, 然后除以2, 因为是按照顶点来的, 所以每条边会被计算两次
- toString 的实现, 可以打印每个顶点, 然后打印这个顶点有连接的顶点.
图的数据结构
图的数据结构, 这里算法很直接明了的给出了答案, 可以使用邻接表数组, 即使用一个数组, 将顶点号当做数组索引, 数组的每一个元素也是一个数据结构, 其中存放着与这个顶点相连接的顶点.
数组中的每一个元素具体使用什么数据结构, 有很多选择, 算法书上使用了第一章里的背包, 是一个用链表实现的背包.
这里要注意的是如果要添加 v-w 边, 要把w添加到v的邻接表中, 再把v添加到w的邻接表中, 每条边会出现两次.
而且还支持平行边和自环, 也就是说邻接表中的元素可能出现重复. 算法这里为了简单, 不会去检测平行边和自环. 使用这种邻接表的数据结构, 唯一有些有趣的地方就是同样的图, 不同的构造顺序会导致实际的邻接表中的顺序有所改变.
来看一个如此实现的Graph数据结构:
public class Graph {
//V是顶点数量
private final int V;
//E是边数
private int E;
//邻接表数组adj
private Bag<Integer>[] adj;
//构造函数, 传入顶点数量, 会初始化长度为V的数组, 并且为每个顶点(索引号)创建一个新的邻接表
public Graph(int V) {
if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
}
public int V() {
return V;
}
public int E() {
return E;
}
//核心函数之一: 添加边
public void addEdge(int v, int w) {
//两条边各添加一次
adj[v].add(w);
adj[w].add(v);
E++;
}
//返回顶点V的相连的点
public Iterable<Integer> adj(int v) {
validateVertex(v);
return adj[v];
}
}
在这个的基础上还可以进行一些改进, 比如使用集合替代Bag, 这样就指明了不允许出现平行边, 删除顶点和添加顶点, 删除一条边之类. 这很可能就不能使用Bag数组, 而需要使用符号表来替代数组.
搜索图的API
关于图的算法, 常见的是已知一幅图, 需要来获取图的性质, 算法里给出了几个常见的处理API:
public class Search
Search(Graph G, int s) //根据图G和顶点s, 构造一个图G中基于顶点s的对象
boolean marked(int v) //检测v和s是否连通
int count() //与S连通的顶点总数
每次用一个图和一个顶点创建一个Search对象, 就可以调用marked算法来检测连通性. 下边就是要根据不同的算法, 创建不同类别的Search对象, 和实现其中的 marked 方法.
在第一章里边的连通性算法, 其实就是解决这个问题的一个途径, 要做的就是从图里取出所有的连接点, 然后将其放入连通分量中, 之后通过连通分量来判断是否连通.
不过这里需要学习一个专用的图算法, 深度优先搜索, 而且是后边图算法的基础.
深度优先搜索 – 连通性问题
深度优先搜索的意思是:
- 将一个顶点标记为已经访问
- 递归的访问它的所有没有被标记过的邻居顶点
这种方法会使用一个布尔数组, 用其中的索引号对应顶点号, 记录所有与给定顶点相连的所有顶点. 如果图是连通的, 所有的顶点最终都会被标记到.
深度优先搜索的每一条边会被查找两次, 第二次的时候会发现该条边已经被搜索过. 所以实际搜索轨迹是总边数的一倍.
深度优先的代码如下:
public class DepthFirstSearch {
//布尔数组
private boolean[] marked;
//记录所有和s连通的顶点的数量
private int count;
//使用G和S创建一个深度优先搜索对象
public DepthFirstSearch(Graph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
//核心方法, 递归搜索
private void dfs(Graph G, int v) {
//每次进入一个新的递归, 就说明新找到一个和s连通的顶点, 所以count++
count++;
//将新找到的顶点标记为true
marked[v] = true;
//在新的顶点的邻接表里遍历所有的顶点, 继续递归调用这个方法, 直到所有的顶点都已经被标记
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
}
//由于在构造对象的时候就使用了dfs, 所以可以直接使用这个方法, 寻找v对应的索引就可以发现是否与s连通了.
public boolean marked(int v) {
return marked[v];
}
}
使用深度优先搜索, 也可以解决一开始的问题, 就是两个点是否连通, 只需要在运行结束之后, 检查布尔数组对应索引的两个值是不是都是true即可. 但是相比连通性算法, 深度优先搜索还可以给出连通算法无法给出的答案, 就是这条路径具体是什么.
路径搜索
路径搜索有点像之前的利用数组索引进行构造一个相连的树的方法.
在之前的深度优先算法里, 每次第一次访问一个连通的边的时候, 就按照对应的索引, 把另一个端点放入到数组的对应的索引里, 比如是从0开始搜索, 遇到2的时候, 就在数组2的位置放入0, 之后2去搜索到第一个3的时候, 在数组3的位置放入2, 这样一直到搜索到想要的节点, 然后反过来用数组不断取数当成索引就可以找到路径.
这算法还真是给力, 要是不从第一章看过来, 就不会立刻理解这个算法, 用数组做成树还真是有意思.
改进的可以返回路径的代码如下, 注意红色的部分:
public class DepthFirstPaths {
private boolean[] marked; // marked[v] = is there an s-v path?
private int count;
//起点
private final int s;
//用数组表示的树
private int[] edgeTo;
public DepthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s);
}
private void dfs(Graph G, int v) {
count++;
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
//w索引的值是v, 对于第一次递归来说, v就是s, 这样就一层一层通过数组可以追查到s
edgeTo[w] = v;
dfs(G, w);
}
}
}
public boolean marked(int v) {
return marked[v];
}
public int count() {
return count;
}
public boolean hasPathTo(int v) {
return marked[v];
}
//其实有了前边的数组, 从v开始不断循环v = edgeTo[v]就可以找到路径
//这里是弄了一个方法专门保存了路径的栈
public Iterable<Integer> pathTo(int v) {
//如果没有路径, 就结束
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<>();
//用循环不断跟着找下去, 直到i=s为止
for (int i = v; i != s; i = edgeTo[i]) {
path.push(i);
}
//循环结束的时候, 所有的除了s之外的路径都被压入栈中, 最后压一个s的值进去
path.push(s);
return path;
}
}
为了要显示路径, 所以要保存一下s的值, 不能像原来的构造器一样直接把s交给dfs进行搜索. 核心的变化就是在dfs第一次找到的时候, 设置数组中与当前顶点值相同的索引值w对应的值, 为上一级节点的值(也就是作为参数的v), 这个技巧和连通算法时候其实一样的.
但是想一想这个递归就可以看出来, 假如连通的话, 肯定会有一条路径能够连通, 但是递归的顺序会影响找到这条路径的方式, 所以找到的路径可能会不同, 也可能不是最短的.
深度优先搜索无法解决这个问题, 因为顾名思义, 这个东西一定是搜索到最深, 不行了, 再从其他的分支返回, 所有的方向都是一搜到底的. 所以就要使用广度优先算法了.
广度优先搜索 – 路径搜索
从深度优先搜索的代码可以看出, 其一路遇到没找过的节点就继续递归, 算法348页的图很好的说明了这点, 会一路找到最深然后逐层返回, 再寻找分支.
广度优先搜索是另外一种方法, 即先搜索最近的一批节点, 再搜索下一批相邻的节点. 其与深度优先搜索不同点就是进入递归之前的处理, 并不是直接进入递归, 而是挨个处理完最近的一批之后再递归, 即递归的顺序与深度优先是不同的.
转换成代码, 实际就是使用一个队列, 将一个节点临近的所有节点都压入队列, 然后处理队列中的点, 不断循环直到队列里没有空, 即无法再向其中添加内容, 也就意味着遍历了所有的点.
写成代码如下:
public class BreadthFirstPaths {
//依然有一个用来记录所有顶点被标记过的数组
private boolean[] marked;
//使用树结构记录路径的数组
private int[] edgeTo;
//作为起点的顶点
private final int s;
//构造器
public BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
//这次是执行bfs广度优先搜索啦, 算法就在这个方法里
bfs(G, s);
assert check(G, s);
}
//广度优先搜索算法
private void bfs(Graph G, int s) {
//先创建一个新的队列
Queue<Integer> q = new Queue<Integer>();
//先将起点标记为true
marked[s] = true;
//然后把s放入到队列里, 即最先处理的就是s顶点
q.enqueue(s);
//只要队列不为空
while (!q.isEmpty()) {
//从队列里弹出最前边的顶点
int v = q.dequeue();
//对这个顶点的所有相邻顶点, 如果第一次处理, 就扔到队列里
for (int w : G.adj(v)) {
//检测如果已经标记, 不做处理
if (!marked[w]) {
//如果未标记, 像深度优先那样使用edgeTo数组作为树来标记
edgeTo[w] = v;
//标记自己已经被遍历过
marked[w] = true;
//将自己放入到队列里
q.enqueue(w);
}
}
}
}
}
其他函数都可以省略, 和之前的深度优先的类似. 这里关键是广度优先不再一直递归到底, 而是始终优先处理最相邻的元素. 在处理完之后, 就得到了edgeTo这个树结构的表示, 其中只要去按照某个索引寻找, 找回S的路径都是最短的.
深度优先搜索 – 连通分量
一幅图可能不是完全连通的, 也可能是完全连通的. 依靠深度优先搜索, 可以获得一个图的连通分量个数, 以及可以判断哪些点是连通的.
这个算法的原理很简单, 无论深度还是广度优先搜索, 都可以遍历完一个连通的图的所有顶点. 所以对于所有的顶点, 都可以执行一次深度优先搜索.
在针对第一个顶点进行深度优先搜索之后, 与其相连的所有顶点都应该被标记了, 只不过不标记true和false了, 可以给予一个数字当做连通分量号. 再对下一个顶点进行搜索的时候, 如果发现顶点已经被标记, 说明这个顶点和之前搜索过的顶点是连通的, 就可以直接跳过, 直到找到下一个没有标记过的顶点, 这就代表一个新的连通分量, 对其搜索完之后, 赋予一个不同的连通分量号.
遍历完所有的顶点之后, 根据标记数就可以知道有几组分量, 而且此时marked数组也变成了第一章的连通分量数组, 检测两个点是否连通, 可以通过索引查找值是否相同来快速确定.
所以这个算法写起来其实挺简单:
public class CC {
//依然是顶点标记数组
private boolean[] marked;
//连通分量数组
private int[] id;
//连通分量号
private int count;
//构造器中
public CC(Graph G) {
marked = new boolean[G.V()];
//获取总的顶点数量的数组
id = new int[G.V()];
//遍历所有顶点, 如果v没有被标记过, 就进行标记
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
//在一次DFS中, 给所有连通的顶点设置的count相同, 下一次则是一个新的count
dfs(G, v);
count++;
}
}
}
//dfs和之前的搜索没有什么本质的不同, 只是加上了将id数组对应的索引设置为count的功能
private void dfs(Graph G, int v) {
marked[v] = true;
id[v] = count;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
}
//方便的通过id数组检测是否连通的方法
public boolean connected(int v, int w) {
return id(v) == id(w);
}
}
算法内部维护了两个数组, 一个marked数组依然用于存放是否标记过, 一个id数组是连通分量数组, marked数组辅助DFS生成id数组.
可见这个方法和第一章的连通分量方法异曲同工之妙.
后边深度优先的几个应用回头再来看吧, 感觉还没有搞清楚是怎么一回事, 对于这些数据结构的应用场景, 很多时候心里还没底.
