DFS和BFS的應(yīng)用-尋找路徑
尋找路徑就是記錄下DFS和BFS訪問(wèn)過(guò)的路徑節(jié)點(diǎn)然后可以通過(guò)這些節(jié)點(diǎn)推出路徑身害。可以查看dfs和bfs算法中保留了路徑草戈。
DFS和BFS的應(yīng)用-尋找連通分量及判斷兩個(gè)是否連通
循環(huán)所有的節(jié)點(diǎn)塌鸯，從第一個(gè)節(jié)點(diǎn)做dfs，如果第一個(gè)節(jié)點(diǎn)做dfs能夠到達(dá)所有節(jié)點(diǎn)唐片，那么就只有一個(gè)連通分量丙猬。否則，第i個(gè)節(jié)點(diǎn)沒(méi)有連通费韭，從第i個(gè)節(jié)點(diǎn)做dfs尋找這個(gè)連通分量淮悼。代碼如下：
private int[] ids;//保存每一個(gè)點(diǎn)所屬的連通分量
public int ConnectedComponent(){
int count=0;
boolean[] marked=new boolean[this.V];
//從第一個(gè)節(jié)點(diǎn)開(kāi)始做dfs，如果第一個(gè)節(jié)點(diǎn)能夠訪問(wèn)全部揽思，那么后面節(jié)點(diǎn)就不需要在dfs了
//如果有的點(diǎn)沒(méi)有marked到袜腥，那么從該點(diǎn)繼續(xù)做dfs，那么這就是第二個(gè)連通分量 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應(yīng)用-查看是否有環(huán)
查找是否有環(huán)也是用的DFS羹令，首先從所有的節(jié)點(diǎn)出發(fā)，關(guān)鍵在于保存上一個(gè)節(jié)點(diǎn)损痰，如果標(biāo)記該節(jié)點(diǎn)已經(jīng)被訪問(wèn)但是他的上一級(jí)不是前一個(gè)節(jié)點(diǎn)福侈，那么表明會(huì)有另一個(gè)節(jié)點(diǎn)到達(dá)，造成有環(huán)的存在
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;
}
}
}
