図論アルゴリズムのDFSとBFS

概要(合計)

DFSはアルゴリズムの中で図論部分の中で最も基本的なアルゴリズムの一つである.アルゴリズムの入門者にとって,これは把握しなければならない基本アルゴリズムである.そのアルゴリズム思想は多くの場所で運用することができ、それを利用して多くの実際の問題を解決することができるが、その原理を深く把握することは私たちが柔軟に運用する鍵である.

意味特徴

DFSは深さ優先探索であり,広さ優先探索に似ており,連通図を遍歴するアルゴリズムでもある.一つの頂点V 0から、一つの道に沿って最後まで歩き続け、目標解に到達できないことを発見したら、前のノードに戻り、別の道から最後まで歩き続けるという、できるだけ奥へ進むという概念が深さ優先の概念である.
再帰的に使用されるため、ノードが特に多く、深さが大きい場合、スタックオーバーフローが発生する可能性があります.解決策は,再帰を非再帰に変更し,自分でスタックを作成することである.
BFSは、広さ優先探索(幅優先探索とも呼ばれる)であり、連通図の遍歴戦略である.一つの頂点V 0から、その周囲の広い領域を放射状に優先的に遍歴することから名付けられた.普通はそれを使って何ができますか?最も直観的な経典の例は迷宮を歩くことであり、私たちは起点から、終点までの最短距離を見つけ、多くの最短経路アルゴリズムは広さ優先の思想に基づいて成立している.

アプリケーションシーン

dfs

連通成分

連通成分:任意の2点が互いに達できる図.
無方向図の連通成分を求めます:O(n)

二分図判定

二分図:各エッジの2つのノードはそれぞれ異なる2つの色をしています.
1つの図が二分図であるか否かを判断する:O(n)

二叉木の再帰的遍歴

bfs

割頂と橋

を求める
切頂:無方向図Gについて、ある点uを削除すると、連通成分数が増加すると、uは切頂となる.
ブリッジ:無方向図Gについて、ある点辺eを削除すると、連通成分数が増加すると、eはブリッジとなる.
すべての図の中の割頂と橋を求めます:
方式1:各ノードを削除し,dfsで連通成分が増加したか否かを判断しようとする.時間複雑度:O(n(n＋m)).
方法2:各ノードに2つのタイムスタンプを記録し、dfsを深く掘り起こす.時間複雑度:O(n+m).
 
　　2.ツリーの階層遍歴

コード実装

/**
* DFS     
*      visit       false
* @param n          
* @param d        
* @return     
*/
bool DFS(Node n, int d){
if (isEnd(n, d)){//              ，   true
return true;
}
for (Node nextNode in n){//  n     nextNode
if (!visit[nextNode]){//
visit[nextNode] = true;//       ，nextNode      
if (DFS(nextNode, d+1)){//       
//      ，         
return true;
}
//     false，                    
visit[nextNode] = false;
}
}
return false;//      
}

/**
*       
* @param Vs   
* @param Vd   
*/
bool BFS(Node& Vs, Node& Vd){
queue Q;
Node Vn, Vw;
int i;
 
//           Q
Q.push(Vs);
hash(Vw) = true;//          ！
 
while (!Q.empty()){//     ，    ！
//      Vn
Vn = Q.front();
 
//      
Q.pop();
 
while(Vw = Vn            ){
if (Vw == Vd){//     ！
//     ，       
return true;//  
}
 
if (isValid(Vw) && !visit[Vw]){
//Vw               
Q.push(Vw);//    Q
hash(Vw) = true;//      
}
}
}
return false;//  
}

 

総括(総)

DFSはこのような問題に適している:初期状態と目標状態を与え、初期状態から目標状態に解があるかどうかを判断することを要求する.

BFSはこのような問題に適している:初期状態と目標状態を与え、初期状態から目標状態への最短経路を要求する.

参考資料

http://rapheal.iteye.com/blog/1526863
http://blog.csdn.net/u011437229/article/details/53188837
http://www.cnblogs.com/George1994/p/6346751.html
転載先:https://www.cnblogs.com/zhongzihao/p/7436660.html