グラフの深さ優先探索またはDFS

深さ優先探索（DFS）は、グラフ走査アルゴリズムです。このアルゴリズムでは、開始頂点が1つ与えられ、隣接する頂点が見つかると、最初にその隣接する頂点に移動し、同じ方法でトラバースを試みます。

可能な限り深さ全体を移動し、その後、バックトラックして前の頂点に到達し、新しいパスを見つけます。

DFSを反復的に実装するには、スタックデータ構造を使用する必要があります。再帰的に実行する場合は、外部スタックは必要ありません。再帰呼び出しの内部スタックで実行できます。

入力 ：グラフの隣接行列。

 A B C D E FA 0 1 1 1 0 0B 1 0 0 1 1 0C 1 0 0 1 0 1D 1 1 1 0 1 1E 0 1 0 1 0 1F 0 0 1 1 1 0 

出力 ：DFSトラバーサル：C F E B D A

アルゴリズム

dfs（vertices、start）

入力 −すべての頂点のリストと開始ノード。

出力 −グラフ内のすべてのノードをトラバースします。

最初に、スタックが空でないときにすべてのノードを非訪問状態にし、スタックから要素をポップしてuに設定すると、uが訪問されていない場合はノードuが表示され、すべてのノードが訪問済みとしてマークされます。私がuに接続しているノードは、i番目の頂点が訪問されていない場合は実行し、次にi番目の頂点をスタックにプッシュします。 
例
 
 #include  #include  using namespace std; #define NODE 6typedef struct node {int val; int状態; // status} node; intgraph [NODE] [NODE] ={{0、1、1、1、0、0}、{1、0、0、1、1、0}、{1、0、0 、1、0、1}、{1、1、1、0、1、1}、{0、1、0、1、0、1}、{0、0、1、1、1、0}}; void dfs（node * vertex、node start）{node u; stack  myStack; for（int i =0; i  
出力
 
 DFSトラバーサル：C F E B D A