在上一篇中我们把图通过邻接表数组表示出来了,这个数据结构将会做我们实现图算法的基础,本篇我们将一起开始学习图算法的第一个搜索算法 - 深度优先搜索
public class Search {
Search(Graph graph, int s);
boolean marked(int v);
int count();
}
在开始实现算法之前,我们依然先来定义搜索的API
假如上图是一个迷宫,我们需要从顶点0开始找到一条出路,假设我们有一条无限长的绳子,和一支粉笔,那么可以这样考虑找到出路:
这种方式绳子总能帮你找到一条出路,而标记不会让你重复走已经走过的通道。
深度优先搜索的实现思路就和走迷宫的方式一样;
public class DepthFirstSearch {
private boolean marked[];
private int count;
public DepthFirstSearch(Graph graph, int s) {
this.marked = new boolean[graph.V()];
this.dfs(graph, s);
}
private void dfs(Graph graph, int v) {
marked[v] = true;
count++;
for (int w : graph.adj(v)) {
if (!marked[w]) {
dfs(graph, w);
}
}
}
@Override
public boolean marked(int v) {
return marked[v];
}
@Override
public int count() {
return count;
}
}
在搜索一张图的时候,使用递归来遍历所有的顶点,在访问其中一个顶点时:
单元测试:
构建下面这张图,然后测试深度优先搜索
@Test
public void test() {
Graph graph = new Graph(8); //构建一张图
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 5);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(4, 3);
graph.addEdge(5, 3);
graph.addEdge(6, 7); //为了展示
SeDepthFirstSearcharch search = new DepthFirstSearch(graph, 0);
System.out.println(search.count());
System.out.println(search.marked(6));
System.out.println(search.marked(7));
System.out.println(search.marked(2));
System.out.println(search.marked(5));
}
以上的递归算法只是一个开始,从上面的结果我们可以看出,我们只能判断出哪些顶点与起点s是连通的,无法给出具体的路径出来;换句话说,我们需要实现从顶点s到顶点v是否存在路径可达,如果存在请打印出来
public class Paths {
Paths(Graph graph, int s);
boolean hasPathTo(int v); //判断出从s->v是否存在路径
Iterable<Integer> pathTo(int v); //如果存在路径,返回路径
}
我们依然基于这张图来看,由于我们需要找出可达的路径,所以我们在进行搜索的时候需要记录下图中的边,这里我们使用的是一个数组edgeTo[],如果存在一条边是v->w,那么可以表示成edgeTo[w]=v,在深度搜索完成之后这个edgeTo[]数组就是一颗由父链表示的一颗树
(父链树在之前的文章中也使用过《如何检测社交网络中两个人是否是朋友关系(union-find算法)》)
public class DepthFirstPaths {
private boolean marked[];
private int[] edgeTo;
private int s;
DepthFirstPaths(Graph graph, int s) {
this.s = s;
this.marked = new boolean[graph.V()];
this.edgeTo = new int[graph.V()];
this.dfs(graph, s);
}
private void dfs(Graph graph, int v) {
this.marked[v] = true;
for (int w : graph.adj(v)) {
if (!marked[w]) {
this.edgeTo[w] = v;
this.dfs(graph, w);
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
throw new IllegalStateException("s不能到达v");
}
Stack<Integer> stack = new LinkedListStack<>();
stack.push(v);
while (edgeTo[v] != s) {
stack.push(edgeTo[v]);
v = edgeTo[v];
}
stack.push(s);
return stack;
}
}
画图来详细跟踪深度优先搜索的运行轨迹,记录了edgeTo的变化以及父链树的逐渐形成
最终父链树形成了,接下来我们来写单元测试校验下生成的父链树和实际的运行结果是否一致
@Test
public void test() {
Graph graph = new Graph(8);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 5);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(4, 3);
graph.addEdge(5, 3);
graph.addEdge(6, 7);
DepthFirstPaths paths = new DepthFirstPaths(graph, 0);
System.out.println(paths.hasPathTo(5));
System.out.println(paths.hasPathTo(2));
System.out.println(paths.hasPathTo(6));
paths.pathTo(5).forEach(System.out::print);
System.out.println();
paths.pathTo(4).forEach(System.out::print);
System.out.println();
paths.pathTo(2).forEach(System.out::print);
}
验证结果完全匹配了父链树
文中所有源码已放入到了github仓库:
https://github.com/silently9527/JavaCore
文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。
最后,写作不易,请不要白嫖我哟,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源??
吐血整理程序员必读书单:https://github.com/silently9527/ProgrammerBooks
通过css3实现炫酷的雷达扫描图: 直接上代码: // index.html!DOCTYPE htmlhtmlh...
1.记忆是很任性的,你想记的总是记不住,你想忘的永远忘不掉。 2.每个百毒不侵...
代码示例 在head标签中添加一行代码: XML/HTML Code 复制内容到剪贴板 html hea...
王诚强,荔枝微课基础架构负责人。热衷于基础技术研发推广,致力于提供稳定高效...
简介: 网游云上网络优化方案 1. 游戏行业背景 1.1 行业概况 2019全球数字游戏营...
在修改一个网页时,会遇到要更换所有网页超链接网址的问题,有时候一个页面的超...
前言 我们在写前面 web页面样式的时候,会发现有些时候,我们怎么修改 style里面...
完整的css代码为 复制代码 代码如下: word-wrap:break-word; overflow:hidden; ...
虽然后来微软对浏览器进行了大量的研发,但事实是现代IE浏览器在大多数时候比基于...
本文示例都是用小程序写的,但是不影响要实现的功能。 wxml 装图片的盒子多复制...