breadth first search c program traverse graph
このチュートリアルでは、グラフまたはツリーが幅優先でトラバースされるC ++での幅優先探索について説明します。また、BFSアルゴリズムと実装についても学習します。
この明示的なC ++チュートリアルでは、ツリーまたはグラフで実行できるトラバーサル手法について詳しく説明します。
トラバーサルは、グラフまたはツリーのすべてのノードにアクセスするために使用する手法です。 トラバーサルには2つの標準的な方法があります。
- 幅優先探索（BFS）
- 深さ優先探索（DFS）
=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。
ソフトウェアでの回帰テストとは
学習内容：
C ++での幅優先探索（BFS）手法
このチュートリアルでは、幅優先探索手法について詳しく説明します。
幅優先探索手法では、グラフまたはツリーが幅優先で探索されます。この手法では、キューデータ構造を使用して、頂点またはノードを格納し、次にどの頂点/ノードを使用するかを決定します。
幅優先アルゴリズムは、ルートノードから開始し、隣接するすべてのノードをトラバースします。次に、最も近いノードを選択し、他のすべての未訪問ノードを探索します。このプロセスは、グラフ内のすべてのノードが探索されるまで繰り返されます。
幅優先探索アルゴリズム
以下に示すのは、BFS手法のアルゴリズムです。
Gを、BFSアルゴリズムを使用してトラバースするグラフと見なします。
Sをグラフのルート/開始ノードとします。
- ステップ1： ノードSから開始し、キューにエンキューします。
- ステップ2： グラフ内のすべてのノードに対して次の手順を繰り返します。
- ステップ3： Sをデキューして処理します。
- ステップ4： Sの隣接するすべてのノードをキューに入れ、それらを処理します。
- (ループの終わり)
- ステップ6： 出口
擬似コード
BFS手法の擬似コードを以下に示します。
Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. endイラスト付きトラバーサル
0を開始ノードまたはソースノードとします。まず、訪問したキューとその隣接するすべてのノードにキューに入れます。
次に、隣接ノードの1つを処理します。つまり、1。キューから削除し、隣接ノードをキューに入れて、訪問済みとしてマークします（2と3はすでにキューにあります）。 0はすでに訪問されているため、無視します。
働くのに最適なビッグデータ企業
次に、ノード2をデキューし、訪問済みとしてマークします。次に、隣接するノード4がキューに追加されます。
次に、キューから3をデキューし、訪問済みとしてマークします。ノード3には、隣接するノードが1つだけあります。つまり、すでにアクセスされている0です。したがって、無視します。
この段階では、ノード4のみがキューに存在します。隣接するノード2はすでにアクセスされているため、無視します。ここで、4を訪問済みとしてマークします。
次に、訪問済みリストに存在するシーケンスは、指定されたグラフの幅優先走査です。
与えられたグラフとトラバーサルシーケンスを観察すると、BFSアルゴリズムの場合、実際にグラフを幅方向にトラバースしてから、次のレベルに進むことがわかります。
BFSの実装
#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '< 出力：
最高評価のyoutubeからmp3へのコンバーター
与えられたグラフの幅優先探索（開始ノードとして0）：
0 1 2 3 4
上記のプログラムでBFSを実装しました。グラフは隣接リストの形式であり、イテレータを使用してリストを反復処理し、BFSを実行することに注意してください。
トラバーサルシーケンスを比較するためのプログラムへの入力として、説明のために使用したものと同じグラフを使用しました。
ランタイム分析
Vが頂点の数で、Eがグラフのエッジの数である場合、BFSの時間計算量は次のように表すことができます。 O（| V | + | E |） 。そうは言っても、グラフを表すために使用するデータ構造にも依存します。
（実装のように）隣接リストを使用する場合、時間計算量は O（| V | + | E |）。
隣接行列を使用する場合、時間計算量は次のようになります。 O（V ^ 2） 。
使用されるデータ構造とは別に、グラフが密に配置されているか、まばらに配置されているかという要因もあります。
頂点の数がエッジの数を超えると、切断された頂点が多数存在するため、グラフはまばらに接続されていると言われます。この場合、グラフの時間計算量はO（V）になります。
一方、グラフのエッジの数が頂点の数よりも多い場合があります。このような場合、グラフは密集していると言われます。このようなグラフの時間計算量はO（E）です。
結論として、式O（| V | + | E |）が意味することは、グラフが密集しているか疎密であるかに依存し、支配的な要因、つまりエッジまたは頂点がグラフの時間計算量を決定します。
BFSトラバーサルのアプリケーション
- ガベージコレクション： ガベージコレクション手法である「チェイニーのアルゴリズム」は、ガベージコレクションをコピーするために幅優先走査を使用します。
- ネットワークでの放送： パケットは、ブロードキャストネットワークのBFS技術を使用して、あるノードから別のノードに移動し、すべてのノードに到達します。
- GPSナビゲーション： GPSナビゲーションでBFSを使用して、隣接または隣接するすべてのロケーションノードを見つけることができます。
- ソーシャルネットワーキングウェブサイト： 人「P」が与えられると、BFSを使用してpからdレベルまでの距離「d」内のすべての人を見つけることができます。
- ピアツーピアネットワーク： この場合も、BFSをピアツーピアネットワークで使用して、隣接するすべてのノードを見つけることができます。
- 重み付けされていないグラフの最短経路と最小全域木： BFS手法を使用して、最短パス、つまり重み付けされていないグラフ内のエッジの数が最も少ないパスを見つけます。同様に、重み付けされていないグラフでBFSを使用して最小全域木を見つけることもできます。
結論
幅優先探索手法は、グラフまたはツリーのすべてのノードを幅方向にトラバースするために使用される方法です。
この手法は主に、グラフのノード間の最短パスを見つけるため、またはネットワークのように隣接するすべてのノードにアクセスする必要があるアプリケーションで使用されます。
=> 無料のC ++コースについては、ここをクリックしてください。
推奨読書