无向图中DFS和BFS的应用

DFS和BFS的应用-寻找路径

寻找路径就是记录下DFS和BFS访问过的路径节点然后可以通过这些节点推出路径。可以查看dfs和bfs算法中保留了路径。

DFS和BFS的应用-寻找连通分量及判断两个是否连通

循环所有的节点，从第一个节点做dfs，如果第一个节点做dfs能够到达所有节点，那么就只有一个连通分量。否则，第i个节点没有连通，从第i个节点做dfs寻找这个连通分量。代码如下：

    private int[] ids;//保存每一个点所属的连通分量
    public int ConnectedComponent(){
        int count=0;
        boolean[] marked=new boolean[this.V];
        //从第一个节点开始做dfs，如果第一个节点能够访问全部，那么后面节点就不需要在dfs了
        //如果有的点没有marked到，那么从该点继续做dfs，那么这就是第二个连通分量 count++；
        for(int i=0;i<this.V;i++){
            if(!marked[i]){
                dfs(marked,ids,i,count);
                count++;
            }
        }
        return count;
    }
    public boolean connected(int v,int w){
        return ids[v]==ids[w];
    }
    private void dfs(boolean[] marked,int[] ids,int v,int count){
        marked[v]=true;
        ids[v]=count;
        for(int w:this.adj[v]){
            if(!marked[w]){
                dfs(marked, ids, w, count);
            }
        }
    }

DFS应用-查看是否有环

查找是否有环也是用的DFS，首先从所有的节点出发，关键在于保存上一个节点，如果标记该节点已经被访问但是他的上一级不是前一个节点，那么表明会有另一个节点到达，造成有环的存在

    private boolean hasCycle;
    public boolean hasCycle(){
        boolean[] marked=new boolean[this.V];
        for(int i=0;i<this.V;i++){
            if(!marked[i])
                hasCycle(marked,i,i);
        }
        return hasCycle;
    }
    public void hasCycle(boolean[] marked,int v,int u){
        marked[v]=true;
        for(int w:this.adj[v]){
            if(!marked[w]){
                hasCycle(marked,w,v);
            }else if(w!=u){
                hasCycle=true;
            }
        }
    }