深度优先遍历与广度优先遍历

前言：从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次称为图的遍历。

深度优先遍历

走迷宫：

   为了更好的理解深度优先遍历，我们先来考虑一下一个经典的问题——走迷宫。

我们使用Tremaux搜索。

• 在身后放一个绳子
• 访问到的每一个地方放一个绳索标记访问到的交会点和通道
• 当遇到已经访问过的地方，沿着绳索回退到之前没有访问过的地

代码实现：

public class DepthFirstSearch {

    private boolean[] marked;
    private int count;
    
    public DepthFirstSearch(Graph G,int S)
    {
        marked=new boolean[G.V()];
        
    }
    
    private void dfs(Graph G,int V)
    {
        marked[V]=true;
        count++;
        for(int w:G.adj(V))
        {
            if(!marked[w])
                dfs(G,w);
        }
    }
    public boolean marked(int w)
    {
        return marked[w];
    }
    
    public int count()
    {
        return count;
    }
    
    
}

深度优先遍历就是用一个递归的方法访问一个顶点，在访问其中一个顶点时，只要

  （1）：将它标记为已经访问；

   （2）:递归的访问它所有没有被标记过的邻居节点。

跟踪算法的行为：

  为了方便描述，我们假设迷宫是由单项通道构成的，在碰到边v-w时，要么递归的进行调用（w没有被访问），要么跳过（w已经被标记）。当再从w-v遇到这条边的时候，总会忽略它，因为另一端V已经访问过了。跟踪图示如下：

现在来分析这张图：

起点为0，查找开始于构造函数调用dfs来标记和访问顶点0，

（1）： 因为2是0的邻接表的第一个元素且没有被访问过，dfs()递归调用自己来访问顶点2，（实际上系统将顶点0和0的邻接表的当前位置压入栈中）。

（2）：顶点0是2的第一个元素但是已经被标记过了，dfs会跳过它，1是2的第二个元素且没有被标记过，dfs()递归调用自己来访问顶点1.（系统将顶点2和2的邻接表的当前位置压入栈中）

（3）对于顶点1，因为它的邻接表的所有顶点均已被访问过，方法从dfs(1)返回，接下来检查2-3，（2的邻接表中1后面是3），dfs()递归调用自己来访问顶点3.

（4）因为5是3的邻接表的第一个元素且没有被访问过，dfs()递归调用自己来访问顶点5.

（5），5的邻接表的所有顶点都已经被标记，不需要在递归。

（6）、因为4是3的邻接表的第二个元素且没有被访问过，dfs()递归调用自己来访问顶点4.

（7）、此时实际上已经遍历完。dfs()不断检查（实际上是出栈），发现所有顶点均标记。

总结：实际上深度优先遍历就是一个不断进栈出栈的过程，对于上面的图遍历，访问某一个顶点，实际上就是将此元素入栈，而元素出栈的条件就是他的邻接表中的所有元素都被标记（访问过）。

利用深度优先遍历，我们可以判断两个顶点之间是否连通：

我们定义以下API：

我们需要定义一个变量来记录已经找的路径。

代码实现：

public class DepthFirstPaths {
   
    private boolean[] marked;
    private int s;
    private int[] edgeTo;
    public DepthFirstPaths(Graph G,int S)
    {
        marked=new boolean[G.V()];
        edgeTo=new int[G.V()];
        this.s=S;
        dfs(G,S);
    }
    
    private void dfs(Graph G,int V)
    {
        marked[V]=true;
        
        for(int w:G.adj(V))
        {
            if(!marked[w])
                edgeTo[w]=V;
                dfs(G,w);
        }
    }
    public boolean hasPathTo(int w)
    {
        return marked[w];
    }
    
    public Iterable<Integer> pathTo(int v)
    {
        if(!hasPathTo(v)) return null;
        Stack<Integer> path=new Stack<Integer>();
        for(int x=v;x!=s;x=edgeTo[x])
        {
            path.push(x);
        }
        path.push(s);
        return path;
    }
    
    
}

　上图中是黑色线条表示深度优先搜索中，所有定点到原点0的路径，他是通过edgeTo[]这个变量记录的，可以从右边可以看出，他其实是一颗树，树根即是原点，每个子节点到树根的路径即是从原点到该子节点的路径。下图是深度优先搜索算法的一个简单例子的追踪。 

算法行为追踪：

//通过遍历，我们想edgeTo[]数组中添加了0-2，2-1，2-3，3-5和3-4.具体分析和上面的分析类似，不再阐述。

广度优先遍历：

现在我们可以通过深度优先遍历来判断顶点S到顶点V是否存在路径，那么如果存在路径，能否找出最小的那一条的呢？事实上，深度优先遍历在解决这个问题上没有什么作用，因为它遍历图的顺序和找出最短路径的目标没有任何关系，而要解决这个问题，就需要用到广度优先遍历。

 要找到S到V的最短路径，从S开始，在所有由一条边到达的定点中就可以寻找V，如果找不到就可以在与S距离两条边的所有顶点中招，以此类推。广度优先遍历就好像一条河流流向迷宫，当遇到交叉路口，河水会分开继续流动，而两股水流相遇时就会合成一股水流！

 我们使用队列来实现相关功能。（用到的API请参考       ）

此算法的核心步骤:

    (1):取队列中的下一个顶点V并标记它

 （2）：将于V相邻的未被标记的顶点加入队列。

代码实现：

public class BreadthFirstSearch {
    
    private boolean[] marked;
    private int s;
    private int edgeTo[];
    public BreadthFirstSearch(Graph g,int s)
    {
        marked=new boolean[g.V()];
        this.s=s;
        edgeTo=new int[g.V()];
        bfs(g,s);
    }
    
    private void bfs(Graph g,int s)
    {  Queue<Integer> queue=new Queue<Integer>();
        marked[s]=true;//标记
        queue.enqueue(s);//起点进队
        
        while(!queue.isEmpty())
        {
            int v=queue.dequeue();
            for(int w:g.adj(v))
            {
                if(!marked[w])
                {   edgeTo[w]=v;
                    marked[w]=true;
                    queue.enqueue(w);
                }
            }
        }
        
    }
    
    public boolean hasPathTo(int v)
    {
        return marked[v];
    }
    
    public Iterable<Integer> pathTo(int v)
    {
        if(!hasPathTo(v)) return null;
        Stack<Integer> path=new Stack<Integer>();
        for(int x=v;x!=s;x=edgeTo[x])
        {
            path.push(x);
        }
        path.push(s);
        return path;
    }//与深度优先遍历一样
    

}

算法行为跟踪：

  首先，标记开始顶点0，加入队列中。

（1），0出队，将他的邻居节点2、1、5依次标记并加入队列。将对应的edgeTo[]设为0；

（2）2出队，检查它的相邻 节点，发现0、1都已经被标记，将3、4标记并加入队列中，将3、4对应的edgeTo设为2；

（3）1出队，检查发现它的所有相邻节点都被标记了。

（4）5出队，检查发现它的所有相邻节点都被标记了。

（5）3出队，检查发现它的所有相邻节点都被标记了。

（6）4出队，检查发现它的所有相邻节点都被标记了。