图算法第二篇 深度优先搜寻与广度优先搜寻及其利用
约定：本文所有波及的图均为无向图，有向图会在之后的文章波及
1.图的存储形式
咱们首先来回顾一下图的存储形式：邻接矩阵和邻接表。为了实现更好的性能，咱们在理论利用中个别应用邻接表的形式来示意图。
具体的实现代码为：
package Graph;import java.util.LinkedList;public class Graph{ private final int V;//顶点数目 private int E;//边的数目 private LinkedList<Integer> adj[];//邻接表 public Graph(int V){ //创立邻接表 //将所有链表初始化为空 this.V=V;this.E=0; adj=new LinkedList[V]; for(int v=0;v<V;++v){ adj[v]=new LinkedList<>(); } } public int V(){ return V;}//获取顶点数目 public int E(){ return E;}//获取边的数目 public void addEdge(int v,int w){ adj[v].add(w);//将w增加到v的链表中 adj[w].add(v);//将v增加到w的链表中 E++; } public Iterable<Integer> adj(int v){ //咱们不用留神这个细节，能够间接把它漠视而不会影响任何对于图的了解与实现 return adj[v]; }}接下来，咱们会首先介绍深度优先搜寻与广度优先搜寻的原理和具体实现；而后依据这两个根本的模型，咱们会介绍六种典型的利用，这些利用只是在深搜和广搜的代码的根底上进行了一些加工，却能够解决不同的问题！
留神：咱们的思路：如何遍历一张图？==>深搜与广搜==>可能解决的问题。
2.深度优先搜寻
深度优先搜寻是利用递归办法实现的。咱们只须要在拜访其中一个顶点时：
- 将它标记为曾经拜访
- 递归地拜访它的所有没有被标记过的街坊顶点
咱们来认真地看一下这个过程：
深度优先搜素大抵能够这样形容：不撞南墙不回头，它沿着一条路始终走上来，直到走不动了而后返回上一个岔路口抉择另一条路继续前进，始终如此，直到走完所有可能达到的中央！它的名字中深度两个字其实就阐明了所有，每一次遍历都是走到最深！
留神一个细节：在咱们下面的最初一个图中，顶点3依然未被标记（绿色）。咱们能够失去以下论断：
应用深度优先搜寻遍历一个图，咱们能够遍历的范畴是所有和终点连通的局部，通过这一个论断，下文咱们能够实现一个判断整个图连通性的办法。
深度优先搜寻的代码实现，我是用Java实现的，其中，我定义了一个类，这样做的目标是更加清晰（毕竟，一会前面还有很多算法）
package Graph;public class DepthFirthSearch { private boolean[] marked;//用来标记顶点 public DepthFirthSearch(Graph G,int s){ //s是终点 marked = new boolean[G.V()]; dfs(G,s); } private void dfs(Graph G,int v){ marked[v]=true;//标记顶点，这是咱们的第一条准则 //对于所有没有被标记的街坊顶点，递归拜访，这时第二条准则 for(int w:G.adj(v)) if(!marked[w]) dfs(G, w); } public boolean marked(int w){ //判断一个顶点是否从终点达到；因为在深搜的过程中，只有被标记了就是可能达到，反正就是不连通的 return marked[w]; } }3.深搜利用(一):查找图中的门路
咱们通过深度优先搜寻能够轻松地遍历一个图，如果咱们在此基础上减少一些代码就能够很不便地查找图中的门路！
比方，题目给定顶点A和顶点B,让你求得从A能不能到达B？如果能，给出一个可行的门路！
为了解决这个问题，咱们增加了一个实例变量edgeTo[]整型数组来记录门路。比方：咱们从顶点A间接达到顶点B,那么就令edgeTo[B]=A，也就是“edge to B is A”，其中A是间隔B最近的顶点且从A能够达到B。我举个简略的例子：
具体的代码如下，其中为了实现这个性能，我定义了一个残缺的类：
package Graph;import java.util.Stack;public class DepthFirstPaths { private boolean [] marked;//记录是否曾经拜访 private int[] edgeTo;//从终点到一个顶点的已知门路上的最初一个顶点 private final int s;//查找的终点 public DepthFirstPaths(Graph G,int s){ //在图G中查找，s是终点 marked = new boolean[G.V()]; edgeTo = new int[G.V()]; this.s=s; dfs(G,s);//递归调用dfs } private void dfs(Graph G,int v){ //从终点v开始查问 marked[v]=true; for(int w:G.adj(v)){ if(!marked[w]){ edgeTo[w]=v;//w的前一个顶点是v dfs(G,w);//既然w没有被标记，就递归地进行dfs遍历它 } } } public boolean hasPathTo(int v){ //判断是否有从终点到顶点v的门路 //如果顶点v被标记了，就阐明它能够达到，否则，就不能够达到 return marked[v]; } //打印门路 public void pathTo(int v){ if(!hasPathTo(v)) System.out.println("不存在门路");; Stack<Integer> path=new Stack<Integer>(); for(int x=v;x!=s;x=edgeTo[x]){ path.push(x); } path.push(s); //打印栈中的元素 while(path.empty()==false) System.out.print(path.pop()+" "); System.out.println(); } }最初一个打印函数pathTo地思维就是通过一个for循环，将门路压到一个栈里，通过栈地先进后出地性质实现反序输入。了解了下面的dfs地过程就好，这里能够独自拿进去去了解。
4.深搜利用(二)：寻找连通重量
还记得咱们上文讲到的dfs的一条性质吗？一个dfs搜寻可能遍历与终点相连通的所有顶点。咱们能够这样思考：申请一个整型数组id[0]用来将顶点分类——“联通的顶点的id雷同，不连通的顶点的id不同”。首先，我对顶点adj[0]进行dfs，把所有可能遍历到的顶点的id设置为0，而后把这些顶点都标记；接下来对所有没有被标记的顶点进行dfs，执行同样的操作，比方将id设为1，这样顺次类推，直到把所有的顶点标记。最初咱们咱们失去的id[]就能够残缺的反映这个图的连通状况。
如果咱们须要判断两个顶点之间是否连通，只须要比拟它们的id即可；同时，咱们还能够依据有多少个不同的id来取得一个图中连通重量的个数，两全其美！
具体的代码实现如下：
package Graph;public class CC { private boolean[] marked; private int [] id;//用于记录连通信息，相当于身份id private int count;//用来判断最终一共有多少个不同的id值 public CC(Graph G){ marked = new boolean[G.V()]; id=new int[G.V()]; for(int s=0;s<G.V();s++){ if(!marked[s]){ dfs(G,s); count++; } } } //以下就是一次残缺的dfs搜寻，它所遍历的顶点都是连通的，对应了同一个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); } } //判断两个顶点是否联通 public boolean connected(int v,int w){ return id[v]==id[w]; } //返回身份id public int id(int v){ return id[v]; } //返回一个图中连通重量的个数，也就是一共有多少个身份id public int count(){ return count; }}5.深搜利用(三):判断是否有环
约定：假如不存在自环和平行边
具体思维：咱们在每次进入dfs的时候，都把父节点传入。比方，咱们要对顶点A进行bfs，则将A的父亲和A一起传入bfs函数，而后在函数外部，如果A的街坊顶点没有被标记，就递归地进行dfs，如果街坊顶点被标记了，并且这个街坊顶点不是顶点A的父节点（咱们有方法判断，因为在每次dfs的时候都将父顶点传入），那么就断定存在环。
说起来不是很好了解，我画了一幅图，你认真跟着每个步骤就必定没问题：
我心愿你本人画一下后果为无环的状况，我置信你的了解会更粗浅！具体的代码如下:
package Graph;public class Cycle { private boolean []marked; private boolean hasCycle; public Cycle(Graph G){ marked = new boolean[G.V()]; for(int s=0;s<G.V();s++){ if(!marked[s]) dfs(G,s,s); } } private void dfs(Graph G,int v,int u){ marked[v]=true; for(int w:G.adj(v)){ if(!marked[w]) dfs(G,w,v); else if(w!=u) hasCycle=true; } } public boolean hasCycle(){ return hasCycle; } }6.深搜利用(四):判断是否为二分图
二分图定义是：可能用两种色彩将图的所有顶点着色，使得任意一条边的两个端点的色彩都不雷同。
对于这个问题，咱们仍然只须要在dfs中减少很少的代码就能够实现。
具体思路：咱们在进行dfs搜寻的时候，但凡碰到没有被标记的顶点时就将它根据二分图的定义标记（使相邻顶点的色彩不同），但凡碰到曾经标记过的顶点，就查看相邻顶点是否不同色。在这个过程中，如果发现存在相邻顶点同色，则不是二分图；如果直到遍历完也没有发现上述同色状况，则是二分图，且上述依据dfs遍历所染的色彩就是二分图的一种。
具体的代码实现:
package Graph;public class TwoColor{ private boolean[] marked; private boolean[] color;//用布尔值代表色彩 private boolean isTwoColorable = true; public TwoColor(Graph G){ marked=new boolean[G.V()]; color=new boolean[G.V()]; for(int s=0;s<G.V();s++){ if(!marked[s]){ dfs(G,s); } } } private void dfs(Graph G,int v){ marked[v]=true; for(int w:G.adj(v)){ if(!marked[w]){ color[w]=!color[v];//如果没有被标记，就依照二分图规定标记 dfs(G,w); } else if(color[w]==color[v]) isTwoColorable=false;//如果被标记就查看 } } public boolean isBipartite(){ return isTwoColorable; }}7.广度优先搜寻
在很多情境下，咱们不是心愿单纯地找到一条连通的门路，而是心愿找到最短的那条，这个时候深搜就不再发挥作用了，咱们接下来介绍另一种图的遍历形式：广度优先搜寻（bfs）。咱们先介绍它的实现，而后再介绍如何寻找最短门路。
广度优先搜寻应用一个队列来保留所有曾经被标记过但其邻接表还未被查看过的顶点。它先将终点退出队列，而后反复以下步骤直到队列为空。
- 取队列中的第一个顶点
v出队 - 将与
v相邻的所有未被标记过的顶点先标记后退出队列
留神：在广度优先搜寻中，咱们并没有应用递归，在深搜中咱们隐式地应用栈，而在广搜中咱们显式地应用队列
一起来看一下具体的过程吧~
直观地讲，它其实就是一种“地毯式”层层推动的搜寻策略，即先查找离起始顶点最近的，而后是次近的，顺次往外搜寻。
我置信你在认真追踪了上图后对广度优先搜寻有了一个残缺的意识，那么接下来我就附上具体的代码实现：
package Graph;import java.util.LinkedList;import java.util.Queue;public class BreadthFirstSearch { private boolean[] marked; private final int s;//终点 public BreadthFirstSearch(Graph G,int s){ marked = new boolean[G.V()]; this.s=s; bfs(G,s); } private void bfs(Graph G,int v){ Queue<Integer> queue = new LinkedList<>(); marked[v]=true;//标记queue终点 queue.add(v);//将终点退出队列 while(!queue.isEmpty()){ int t=queue.poll();//从队列中删去下一个顶点 for(int w:G.adj(t)){ if(!marked(w)){ //对于每个没有被标记的相邻顶点 marked[w]=true;//标记它 queue.add(w);//并将它增加到队列 } } } } public boolean marked(int w){ return marked[w]; }}8.广搜利用(一):查找最短门路
其实只有在广度优先搜寻的过程中增加一个整型数组edgeTo[]用来存储走过的门路就能够轻松实现查找最短门路，因为其原理和广搜中的edgeTo[]完全一致，所以这里我就不多说了。
以下是具体的代码实现：
package Graph;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;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()]; this.s=s; bfs(G,s); } private void bfs(Graph G,int v){ Queue<Integer> queue = new LinkedList<>(); marked[v]=true;//标记queue终点 queue.add(v);//将终点退出队列 while(!queue.isEmpty()){ int t=queue.poll();//从队列中删去下一个顶点 for(int w:G.adj(t)){ if(!marked(w)){ edgeTo[w]=t;//保留最短门路的最初一条边 //对于每个没有被标记的相邻顶点 marked[w]=true;//标记它 queue.add(w);//并将它增加到队列 } } } } public boolean marked(int w){ return marked[w]; } public boolean hasPathTo(int v){ //判断是否有从终点到顶点v的门路 //如果顶点v被标记了，就阐明它能够达到，否则，就不能够达到 return marked[v]; } public void pathTo(int v){ if(!hasPathTo(v)) System.out.println("不存在门路");; Stack<Integer> path=new Stack<Integer>(); for(int x=v;x!=s;x=edgeTo[x]){ path.push(x); } path.push(s); //打印栈中的元素 while(path.empty()==false) System.out.print(path.pop()+" "); System.out.println(); }}9.广搜利用(二)：求任意两顶点间最小间隔
构想这样一个问题：给定图中任意两点（u，v），求解它们之间距离的最小边数。
咱们的想法是这样的：以其中一个顶点（比方u）为终点，执行bfs，同时申请一个整型数组distance[]用来记录bfs遍历到的每一个顶点到终点u的最小间隔。
要害：假如在bfs期间，顶点x从队列中弹出，并且此时咱们会将所有相邻的未拜访顶点i{i1,i2……}推回到队列中，同时咱们应该更新distance [i] = distance [x] + 1;。它们之间的间隔差为1。咱们只须要在每一次执行上述进出队列的时候执行这个递推关系式，就能保障distance[]中记录的间隔值是正确的！！
请务必认真思考这个过程，咱们很快乐只有保障这一点，就能够达到咱们计算最短距离的目标。
以下是咱们的代码实现：
package Graph;import java.util.LinkedList;import java.util.Queue;public class getDistance { private boolean[] marked; private int [] distance;//用来记录各个顶点到终点的间隔 private final int s;//终点 public getDistance(Graph G,int s){ marked = new boolean[G.V()]; distance= new int[G.V()]; this.s=s; bfs(G,s); } private void bfs(Graph G,int v){ Queue<Integer> queue = new LinkedList<>(); marked[v]=true;//标记queue终点 queue.add(v);//将终点退出队列 while(!queue.isEmpty()){ int t=queue.poll();//从队列中删去下一个顶点 for(int w:G.adj(t)){ if(!marked(w)){ //对于每个没有被标记的相邻顶点 marked[w]=true;//标记它 queue.add(w);//并将它增加到队列 distance[w]=distance[t]+1;//这里就是须要增加递推关系的中央！ } } } } public boolean marked(int w){ return marked[w]; //打印，对于一个给定的顶点，咱们能够取得间隔它特定长度的顶点 public void PrintVertexOfDistance(Graph G,int x){ for(int i=0;i<G.V();i++){ if(distance[i]==x){ System.out.print(i+" "); } } System.out.println(); } }通过下面的办法，咱们能够很容易的实现求一个人的三度好友之类的问题，我专门写了一个打印的函数（在下面代码片段最初），它接管一个整型变量int v,能够打印出所有到终点间隔为v的顶点。
10.后记
好了，对于图的内容就到这里了，我心愿通过这篇文章你对于图的深搜和广搜有了一个粗浅的意识！记得入手写代码哦~下一篇文章，小超与你不见不散！
码字和绘制原理图很不容易，如果感觉本文对你有帮忙，关注作者就是最大的反对！棘手点个在看更感激不尽！因为，这将是小超持续创作的能源，毕竟，做任何事件都是要有反馈的~
最初欢送大家关注我的公众号：小超说，之后我会持续创作算法与数据结构以及计算机基础知识的文章。也能够加我微信 chao_hey，咱们一起交换，一起提高！