第二次来图算法了, 这次比原来的理解程度又要深一些了, 当然还有一些连通图问题可能用数组等其他方式来解决也可以.
这次是简单一点的图算法, 但是为了掌握, 都是自己对着算法写出来的, 想用那些高级算法,还是得先把基础算法的原理掌握透彻.
- 图算法类的接口
- 图算法 - 广度优先遍历
- 图算法 - 深度优先遍历
- 图算法 - 寻最短路径
- 图算法 - 寻最优路径
- 图算法 - 寻找拓扑序
图算法类的接口
每种算法就是一个图的一个方法, 因此可以用一个接口来表示. 接口中的方法则取决于我们想要采用的算法. 主要有如下的内容:
- 广度优先遍历
- 深度优先遍历
- 拓扑序
- 最短路线
- 最优路线
public interface GraphAlgorithms<T> {
QueueInterface<T> getBreadthFirstTraversal(T origin);
QueueInterface<T> getDepthFirstTraversal(T origin);
Stack<T> getTopologicalOrder();
int getShortestPath(T begin, T end, Stack<T> path);
double getCheapestPath(T begin, T end, Stack<T> path);
}
这其中都使用了之前编写的数据结构, 使用Java提供的也可以.
下边就来一点一点看一下如何实现.
图算法 - 广度优先遍历
在遍历树的时候, 已经采取过了广度优先遍历, 由于树是特殊的有向图, 不会存在环或者说无向, 那么在遍历的时候, 就不用管是否已经访问过, 一个树的子节点是无论如果也不可能先于父节点被放入队列,
遍历图就不行了, 从起点开始, 必须对周围的点放入队列后进行标记, 然后再继续对没有放入队列的点进行同样的操作, 这个方法还是挺简单的.
@Override
public QueueInterface<T> getBreadthFirstTraversal(T origin) {
//第一个队列, 用于存放顶点
QueueInterface<VertexInterface<T>> temp = new ArrayQueue<>();
//第二个队列, 用于返回队列标识给客户, 不能直接返回VertexInterface类.
QueueInterface<T> result = new ArrayQueue<>();
//获取初始顶点
VertexInterface<T> start = vertices.get(origin);
//标记为已访问
start.isVisited();
//放入队列
temp.enqueue(start);
//开始弹出队列, 只要不为空就反复弹, 每次弹的时候将T放入result, 然后将弹出的顶点的所有unvisited的邻接点放入temp队列中.
while (!temp.isEmpty()) {
//从队列中弹出一个顶点
VertexInterface<T> currentVertex = temp.dequeue();
//检测所有邻居, 如果未访问过, 标记为已经访问然后放入队列
Iterator<VertexInterface<T>> neighbors = currentVertex.getNeighborIterator();
while (neighbors.hasNext()) {
VertexInterface<T> aNeighbor = neighbors.next();
if (!aNeighbor.isVisited()) {
//这个地方是关键, 如果要对顶点进行一些操作, 就可以写在这个代码里. 我们这里进行的操作就是记录遍历的顶点顺序.
aNeighbor.visit();
temp.enqueue(aNeighbor);
}
}
result.enqueue(currentVertex.getLabel());
}
//得到了结果之后, 重置图状态, 这个也可以不写在里边, 由客户手工调用.
resetVertices();
//当temp弹完的时候, result里应该都进去了, 因为这个循环是每次从temp中拿一个, 再放入result中一个.
return result;
}
广度优先遍历对于有环和无环图都是可以用的, 即使图分割为几个不连通的部分, 也可以适用, 只不过只能得到与该顶点相连接的图.
图算法 - 深度优先遍历
与深度遍历树类似的是, 要一直去找到遍历到某一个路径的最末尾, 也就是不包含任何邻居的点或者包含邻居但全部被访问完毕. 这里还需要注意的是, 遍历只是一个顺序, 取决于何时进行操作.
考虑与广度优先不同的做法, 即不能一次塞完全部的邻居, 而是每新到一个点都要立刻再去访问邻居, 如果没有了再去访问另外一个邻居.
具体来实现的时候, 很像树的做法, 先把一个顶点入栈, 然后将其所有未访问邻居入栈, 直到某个顶点没有未访问的邻居, 就将其出栈. 实际的访问顺序发生在入栈的时候.
来写一下:
@Override
public QueueInterface<T> getDepthFirstTraversal(T origin) {
//第一个栈, 用于存放顶点
Stack<VertexInterface<T>> temp = new LinkedListStack<>();
//第二个队列, 用于返回结果, 每次入栈的时候, 把那个顶点标签放入到result中.
QueueInterface<T> result = new ArrayQueue<>();
//先把起点的标签放入结果队列中
result.enqueue(origin);
//获取初始顶点
VertexInterface<T> start = vertices.get(origin);
//标记为已访问
start.isVisited();
//放入栈中
temp.push(start);
//只要栈不空
while (!temp.isEmpty()) {
//寻找栈顶的顶点
VertexInterface<T> currentVertex = temp.peek();
//将所有未访问的点标记为已访问然后入栈, 每入栈一个, 在result中进行记录.
//如果全部都已经访问, 则需要弹出当前点
Iterator<VertexInterface<T>> neighbors = currentVertex.getNeighborIterator();
boolean allVisited = true;
while (neighbors.hasNext()) {
VertexInterface<T> aNeighbor = neighbors.next();
//注意这里, 只要放入一个就足够了, 然后立刻break
if (!aNeighbor.isVisited()) {
allVisited = false;
aNeighbor.visit();
temp.push(aNeighbor);
result.enqueue(aNeighbor.getLabel());
break;
}
}
//如果循环跑完了一个都没放进去, 则弹出当前顶点
if (allVisited) {
temp.pop();
}
}
//栈空之后, 所有的顶点及其邻居都进来过了, 返回 result即可
resetVertices();
return result;
}
利用了栈, 就可以实现回溯, 一定要记住这个结论. 每次只放入一个点, 然后就立刻对栈执行操作, 就可以起到进入分支但是还可以回溯的效果.
图算法 - 寻最短路径
很多算法都是搭建在深度优先和广度优先基础上的, 比如这个寻最短路径.
想一想, 如果要寻最短路径该如何寻找呢, 从一个点出发, 将其所有的邻居的前驱节点标记上自己, 然后将距离标记1. 然后继续对每个点进行如此的操作. 每次距离都是前驱节点的距离+1.
然后可能会通过若干个点都能连接到目标路径, 就将这若干个点先暂时放着, 直到遍历结束.
此时比较一下这若干个点自己的距离如何, 选取其中距离最小的点, 这就是通往最终目标的最后一个点, 然后返回完整的路径即可.
来尝试自己写一下看看:
//获取最短路径长度和路径栈
@Override
public int getShortestPath(T begin, T end, Stack<T> path) {
//只需要用到一个队列
QueueInterface<VertexInterface<T>> temp = new ArrayQueue<>();
//获取初始顶点
VertexInterface<T> start = vertices.get(begin);
VertexInterface<T> endVertex = vertices.get(end);
//进行初始判断, 是不是相同. 相同就往栈中加入开始节点的标签, 然后结束
if (start.equals(endVertex)) {
path.push(endVertex.getLabel());
resetVertices();
return 0;
}
//标记为已访问
start.isVisited();
//这里将距离当成cost, 起点相距起点自然是0
start.setCost(0);
//把起点放入队列
temp.enqueue(start);
//开始进行广度优先搜索
while (!temp.isEmpty()) {
//从队列中弹出一个顶点
VertexInterface<T> currentVertex = temp.dequeue();
//有了前边的判断, 顶点一定不是要找的点, 就开始找邻居
Iterator<VertexInterface<T>> neighbors = currentVertex.getNeighborIterator();
//对于每个邻居顶点, 如果就是目标, 则要填充栈并返回, 如果不是, 则要设置前驱节点然后增加路径长度
while (neighbors.hasNext()) {
VertexInterface<T> aNeighbor = neighbors.next();
//这里进行判断, 如果某个邻居节点就是要找的点, 直接返回邻居的路径长度+1即可
//还需要在栈中装载整条路径, 这个类似链表, 不断把节点标签写入即可.
if (aNeighbor.equals(endVertex)) {
int length = (int) (currentVertex.getCost() + 1);
path.push(aNeighbor.getLabel());
while (currentVertex != null) {
path.push(currentVertex.getLabel());
currentVertex = currentVertex.getPredecessor();
}
resetVertices();
return length;
}
//如果不是要找到的点, 需要额外添加一些步骤
if (!aNeighbor.isVisited()) {
aNeighbor.visit();
//这里需要增加一些步骤:
//设置新入队的顶点的前驱节点是刚弹出队的顶点
aNeighbor.setPredecessor(currentVertex);
//设置新入队的顶点的距离是前驱节点+1
aNeighbor.setCost(currentVertex.getCost() + 1);
temp.enqueue(aNeighbor);
}
}
}
//能走到这一步, 说明整个遍历过程都没有找到, 重置状态然后返回-1即可
resetVertices();
return -1;
}
图算法 - 寻最优路径
在广度优先遍历寻找最短路径的时候, 无需去统计所有可以通向这个节点的路径, 因为是最短而且无权, 只要是先找到的一条路, 就必定是最短的, 无需再去寻找其他的路径.
但是加上权就不是了, 这个算法就别自己想了, 看一下经典的Dijkstra算法, 需要使用一个优先队列, 然后从第一个点开始, 不断使用优先队列排列所有最短路径的点, 然后按这个顺序继续出队入队.
每次入队的时候, 需要将前驱节点设置为上一个点, 每次出队的时候, 需要更新那个点才可以. 到最后找到目标点, 就找到了路径.
为了实现这个算法,先要创建一个内部类, 用来封装顶点, 到这个顶点的权重, 以及前驱节点, 然后这个内部类就是优先队列中装的元素.
优先队列的排序原则是, 内部类中权重越小就排在越优先的位置. 正好符合我们的要求. 先逐个创建需要的东西.
首先是一个从顶点获取其到某个顶点的边的权重的方法, 这个方法可以将其加在VertexInterface中, 然后给实现出来.
public interface VertexInterface<T> {
//获取当前顶点到指定点的权重
double getWeightToVertex(VertexInterface<T> target);
}
然后给实现出来:
public double getWeightToVertex(VertexInterface<T> target) {
for (Edge edge : edgeList) {
if (edge.vertex.equals(target)) {
return edge.weight;
}
}
return -1;
}
这个方法说明我们的权重不能为负数. 这也是Dijkstra算法的要求. 由于我们一定是在Neighbor中查找, 所以这个方法肯定可以返回权重, 而不是找不到对应的点.
然后在DirectWeightedGraph<T>类中准备一个内部类, 用于之前说的放入到优先队列的数据结构中:
private class Entry implements Comparable<Entry> {
private VertexInterface<T> currentVertext;
private double totalWeight;
private VertexInterface<T> predecessor;
public Entry(VertexInterface<T> currentVertext, double totalWeight, VertexInterface<T> predecessor) {
this.currentVertext = currentVertext;
this.totalWeight = totalWeight;
this.predecessor = predecessor;
}
@Override
public String toString() {
return "Entry{" +
"currentVertext=" + currentVertext +
", totalWeight=" + totalWeight +
", predecessor=" + predecessor +
'}';
}
//这个方法很关键, Java的PriorityQueue默认是优先移除小的, 即按照升序排列
@Override
public int compareTo(Entry entry) {
return (int) (this.totalWeight - entry.totalWeight);
}
}
在上边的两个东西的辅助之下, 就可以来写算法了:
//最优路线 - Dijkstra算法
@Override
public double getCheapestPath(T begin, T end, Stack<T> path) {
//创建一个优先队列
PriorityQueue<Entry> entries = new PriorityQueue<>();
//先获取起点, 然后包装一个类扔进优先队列
VertexInterface<T> startVertex = vertices.get(begin);
VertexInterface<T> endVertex = vertices.get(end);
Entry firstEntry = new Entry(startVertex, 0, null);
entries.add(firstEntry);
//寻找标志
boolean found = false;
//只要还没找到并且entries不为空
while (!found && !entries.isEmpty()) {
//从优先队列里弹出一项
Entry anEntry = entries.remove();
//如果这一项其中的顶点还没有被访问过
if (!anEntry.currentVertext.isVisited()) {
VertexInterface<T> currentVertex = anEntry.currentVertext;
//先标记访问, 然后将Entry中的总权重和前驱都给这个顶点设置上
currentVertex.visit();
currentVertex.setCost(anEntry.totalWeight);
currentVertex.setPredecessor(anEntry.predecessor);
//如果优先队列里弹出来的就是目标, 设置好前驱后, 这个分支直接就导致循环结束了
if (currentVertex.equals(endVertex)) {
found = true;
} else {
//遍历这个顶点的所有邻居, 如果被访问过, 就忽略; 如果没有访问过, 需要计算当前点的cost加到邻居的权重, 两个相加算出那个邻居的总权重, 然后包装一个新的对象扔进去
Iterator<VertexInterface<T>> neighbors = currentVertex.getNeighborIterator();
while (neighbors.hasNext()) {
VertexInterface<T> anNeighbor = neighbors.next();
if (!anNeighbor.isVisited()) {
//获取权重
double totalWeight = currentVertex.getWeightToVertex(anNeighbor) + currentVertex.getCost();
//将邻居节点, 到这个邻居节点的总权重, 前驱节点=当前节点包装对象扔进优先队列.
Entry newEntry = new Entry(anNeighbor, totalWeight, currentVertex);
entries.add(newEntry);
}
}
}
}
}
//运行到这里检测是否寻找到
if (found) {
double weight = endVertex.getCost();
while (endVertex != null) {
path.push(endVertex.getLabel());
endVertex = endVertex.getPredecessor();
}
resetVertices();
return weight;
} else {
resetVertices();
return -1;
}
}
这里有意思的是, 如果当前节点扔到优先队列的总权重, 比某些节点也扔了同样的节点, 但是权重更高的会排在前边, 一旦访问了, 权重更高的那个节点就会被舍弃. 这就是优先队列的好处.
虽然用脑子很难想出来多节点的时候怎么办, 不过确实能够计算出来结果, 确实有意思. Dijkstra算法适用于单源的有向/无向带权图.
图算法 - 寻找拓扑序
拓扑序就是指将顶点排成一行, 其中每个边都指向其后边的某个结点. 所以有环图是没有拓扑序的, 一般拓扑序用于有向无环图. 对于同一个图, 未必只有一种拓扑序.
拓扑序反向来看, 排在末尾的一定是没有任何邻居(或者说后续顶点)的顶点, 然后是所有的邻居都被访问的未访问顶点, 然后一直反向推回去.
所以可以从任意一个点开始, 只要这个点没有邻居或者所有邻居都访问过了, 就将其压入栈, 否则继续执行下一个顶点, 直到所有顶点都压入了栈, 此时栈中就是拓扑序.
来写成代码试试:
//获取有向无环图的拓扑序
@Override
public Stack<T> getTopologicalOrder() {
//创建结果栈
Stack<T> result = new LinkedListStack<>();
//获取顶点的个数.
int count = vertices.size();
//只要还有顶点没有压完就一直循环着
while (count != 0) {
//每次循环都遍历一次全部的顶点, 只要这个顶点没有被访问, 并且无邻居或者邻居全部被访问完, 就标记访问并压入栈.
for (VertexInterface<T> vertex : vertices.values()) {
if (!vertex.isVisited() && isAllNeighborVisited(vertex)) {
vertex.visit();
result.push(vertex.getLabel());
count--;
}
}
}
resetVertices();
return result;
}
//判断一个顶点的所有邻居都已经被访问或者无邻居的辅助方法
private boolean isAllNeighborVisited(VertexInterface<T> vertex) {
boolean result = true;
//没有邻居也返回true
if (!vertex.hasNeighbor()) {
return true;
}
Iterator<VertexInterface<T>> interfaceIterator = vertex.getNeighborIterator();
while (interfaceIterator.hasNext()) {
if (!interfaceIterator.next().isVisited()) {
result = false;
break;
}
}
return result;
}
这样就可以得到一种拓扑序, 如果顶点比较多的话, 顶点的排列顺序其实会影响实际所得的拓扑序, 不过任意一种拓扑序都能解决问题.
至此为止又把Java的数据结构和算法过了一遍, 其中的散列表的线性探查法和红黑树还没有仔细看, 不过这一遍一过, 数据结构有所加强.
剩下就是要把算法设计手册第二版再过一下, 然后遇到一些高级的算法和技巧注意掌握和总结了.
另外也可以考虑C语言的算法了, 今天给女儿摇了宝山世外, 不管最后结果如何, 博一把还是对的, 写完这篇博文的时候女儿已经熟睡, 希望她能成功摇中. 晚安, 我亲爱的老婆和女儿.
