算法之美-DFS与BFS的比较

什么时候用DFS什么时候有用BFS呢

DFS与BFS都可以把所有直接或间接相连接的点都遍历到，但是因为机制的不一样所以用处也会有所不同。

DFS(深度优先)一般仅仅用于求一个图有多少个联通分量，看看两个结点之间是否互相连接。

注意:一般已经确定了某几个点之间是互相联通的情况下，就应该不要考虑使用DFS去解决问题了，因为会有更好的策略。

一般情况下，我们认为使用递归的DFS，可以求得能到达的最远距离，因为递归从一个结点开始会一只走到头，直到走不通再返回，好像看起来可以求出来最长的一条路径。

 

BFS(广度优先)通过队列，把与某个结点直接相连的结点都存入队列中，按照与原结点的距离的近远再依次遍历间接相连的结点。广度优先本身就是用来处理最短与最长路径的问题。

总结：一般求图的联通性的时候才会使用深度，其他的情况都可以用广度来代替深度。有些问题让求到达的最远的距离，或是求能受到影响到的范围，因为只要是相连接的点，不管是直接还是间接，肯定已经相连了，所以用广度就可以解决问题了。

有些问题，点与点之间连接在一起的条件是不确定的，在某些条件下是相连的，有可能在其他条件下就不会连接在一起了，这时候只能考虑深度了...(邻接表与邻接矩阵都是表示图中点与点相连状态的)

所以广度的一般深度都可以实现，但是有些问题只能深度来实现了。

 

经典案例

深度遍历与广度遍历是可以相互转换的，每个点的连接情况对于出发结点而言都是不同的，比如说7结点，不能确定到底与图中哪个结点是相连，需要根据具体的情况来判断的。比如从7结点出发，7结点和8结点不是相连的，而从8结点出发，7结点和8结点就是相连的了。

当我们把图中的所有的点的连接情况进行加工都表示出来之后，就可以使用广度优先了。

总之已经明确了图中点与点之间互相连接的关系，就可以使用广度了...

示例：

只能从高的数字往低的数字移动，计算可以移动的最大距离

 4 4
 7 8 9 10
 6 15 16 11
 5 14 13 12
 4 3 2 1

邻接矩阵

public class DGraph {
    static int[][] arr;
    static int MaxCount;
    static boolean visited[][];
    static int Count;
    static int N=0;
    static int M=0;
    static int answer=0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		 N = sc.nextInt();//点的个数
		  M = sc.nextInt();
		 arr = new int[N][M];
		 
	   for(int j =0;j