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;
}
}
}
