3.4.2 广度优先搜索
所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。
API 设计：
代码
public class BreadthFirstSearch { //索引代表顶点，值表示当前顶点是否已经被搜索 private boolean[] marked; //记录有多少个顶点与s顶点相通 private int count; //用来存储待搜索邻接表的点 private Queue<Integer> waitSearch; //构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点 public BreadthFirstSearch(Graph G, int s) { //创建一个和图的顶点数一样大小的布尔数组 marked = new boolean[G.V()]; //初始化待搜索顶点的队列 waitSearch = new Queue<Integer>(); //搜索G图中与顶点s相同的所有顶点 dfs(G, s); } //使用广度优先搜索找出G图中v顶点的所有相邻顶点 private void dfs(Graph G, int v) { //把当前顶点v标记为已搜索 marked[v]=true; //把当前顶点v放入到队列中，等待搜索它的邻接表 waitSearch.enqueue(v); //使用while循环从队列中拿出待搜索的顶点wait，进行搜索邻接表 while(!waitSearch.isEmpty()){ Integer wait = waitSearch.dequeue(); //遍历wait顶点的邻接表，得到每一个顶点w for (Integer w : G.adj(wait)) { //如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点 if (!marked[w]) { dfs(G, w); } } } //相通的顶点数量+1 count++; } //判断w顶点与s顶点是否相通 public boolean marked(int w) { return marked[w]; } //获取与顶点s相通的所有顶点的总数 public int count() { return count; } }
3.5 案例-畅通工程续1
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。目前的道路状况，9号城市和10号城市是否相通？9号城市和8号城市是否相通？
在我们的测试数据文件夹中有一个trffic_project.txt文件，它就是诚征道路统计表，下面是对数据的解释：
总共有 20个城市，目前已经修改好了7条道路，问9号城市和10号城市是否相通？9号城市和8号城市是否相通？
解题思路：
1.创建一个图Graph对象，表示城市；
2.分别调用addEdge(0,1),addEdge(6,9),addEdge(3,8),addEdge(5,11),addEdge(2,12),addEdge(6,10),addEdge(4,8)，表示已经修建好的道路把对应的城市连接起来；
3.通过Graph对象和顶点9，构建DepthFirstSearch对象或BreadthFirstSearch对象；
4.调用搜索对象的marked(10)方法和marked(8)方法，即可得到9和城市与10号城市以及9号城市与8号城市是否相通。
代码：
import java.io.BufferedReader; import java.io.InputStreamReader; public class Traffic_Project2 { public static void main(String[] args) throws Exception { //创建输入流 BufferedReader reader = new BufferedReader(new InputStreamReader(Traffic_Project2.class.getClassLoader().getResourceAsStream("traffic_project.txt"))); //读取城市数目，初始化Graph图 int number = Integer.parseInt(reader.readLine()); Graph G = new Graph(number); //读取已经修建好的道路数目 int roadNumber = Integer.parseInt(reader.readLine()); //循环读取已经修建好的道路，并调用addEdge方法 for (int i = 0; i < roadNumber; i++) { String line = reader.readLine(); int p = Integer.parseInt(line.split(" ")[0]); int q = Integer.parseInt(line.split(" ")[1]); G.addEdge(p, q); } //根据图G和顶点9构建图的搜索对象 //BreadthFirstSearch search = new BreadthFirstSearch(G,9); DepthFirstSearch search = new DepthFirstSearch(G, 9); //调用搜索对象的marked(10)方法和marked(8)方法 boolean flag1 = search.marked(10); boolean flag2 = search.marked(8); System.out.println("9号城市和10号城市是否已相通：" + flag1); System.out.println("9号城市和8号城市是否已相通：" + flag2); } }
3.6 路径查找
在实际生活中，地图是我们经常使用的一种工具，通常我们会用它进行导航，输入一个出发城市，输入一个目的地城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市。这类问题翻译成专业问题就是：从s顶点到v顶点是否存在一条路径？如果存在，请找出这条路径。
例如在上图上查找顶点 0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4。
3.6.1 路径查找API设计
3.6.2 路径查找实现
根据图G和顶点9构建图的搜索对象我们实现路径查找，最基本的操作还是得遍历并搜索图，所以，我们的实现暂且基于深度优先搜索来完成。其搜索的过程是比较简单的。我们添加了edgeTo[]整型数组，这个整型数组会记录从每个顶点回到起点s的路径。如果我们把顶点设定为0，那么它的搜索可以表示为下图：
根据最终 edgeTo的结果，我们很容易能够找到从起点0到任意顶点的路径；
public class DepthFirstPaths { //索引代表顶点，值表示当前顶点是否已经被搜索 private boolean[] marked; //起点 private int s; //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点 private int[] edgeTo; //构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径 public DepthFirstPaths(Graph G, int s){ //创建一个和图的顶点数一样大小的布尔数组 marked = new boolean[G.V()]; //创建一个和图顶点数一样大小的整型数组 edgeTo = new int[G.V()]; //初始化顶点 this.s=s; //搜索G图中起点为s的所有路径 dfs(G,s); } //使用深度优先搜索找出G图中v顶点的所有相邻顶点 private void dfs(Graph G, int v){ //把当前顶点标记为已搜索 marked[v]=true; //遍历v顶点的邻接表，得到每一个顶点w for (Integer w : G.adj(v)){ //如果当前顶点w没有被搜索过，则将edgeTo[w]设置为v,表示w的前一个顶点为v，并递归搜索与w顶点相通的其他顶点 if (!marked[w]){ edgeTo[w]=v; dfs(G,w); } } } //判断w顶点与s顶点是否存在路径 public boolean hasPathTo(int v){ return marked[v]; } //找出从起点s到顶点v的路径(就是该路径经过的顶点) public Stack<Integer> pathTo(int v){ //当前v顶点与s顶点不连通，所以直接返回null，没有路径 if (!hasPathTo(v)){ return null; } //创建路劲中经过的顶点的容器 Stack<Integer> path = new Stack<Integer>(); //第一次把当前顶点存进去，然后将x变换为到达当前顶点的前一个顶点edgeTo[x],在把前一个顶点存进去，继续将x变化为到达前一个顶点的前一个顶点，继续存，一直到x的值为s为止，相当于逆推法，最后把s放进去 for (int x = v;x!=s;x=edgeTo[x]){ //把当前顶点放入容器 path.push(x); } //把起点s放入容器 path.push(s); return path; } } //测试代码 public class DepthFirstPathsTest { public static void main(String[] args) throws Exception { //创建输入流 BufferedReader reader = new BufferedReader(new InputStreamReader(DepthFirstPathsTest.class.getClassLoader().getResourceAsStream("road_find.txt"))); //读取城市数目，初始化Graph图 int number = Integer.parseInt(reader.readLine()); Graph G = new Graph(number); //读取城市的连通道路 int roadNumber = Integer.parseInt(reader.readLine()); //循环读取道路，并调用addEdge方法 for (int i = 0; i < roadNumber; i++) { String line = reader.readLine(); int p = Integer.parseInt(line.split(" ")[0]); int q = Integer.parseInt(line.split(" ")[1]); G.addEdge(p, q); } //根据图G和顶点0路径查找对象 DepthFirstPaths paths = new DepthFirstPaths(G, 0); //调用查找对象的pathTo(4)方法得到路径 Stack<Integer> path = paths.pathTo(4); //遍历打印 StringBuilder sb = new StringBuilder(); for (Integer v : path) { sb.append(v+"-"); } sb.deleteCharAt(sb.length()-1); System.out.println(sb); } }
