dfsearch
グラフの深さ優先検索
構文
説明
例
入力引数
出力引数
ヒント
dfsearch
およびbfsearch
は有向グラフと無向グラフを同様に扱います。ノードs
とノードt
の間の無向エッジは、s
からt
へと、t
からs
への双方向エッジと同様に扱われます。
アルゴリズム
深さ優先検索アルゴリズムは開始ノード s
から開始し、最小のノード インデックスをもつ s
の隣接ノードを検査します。次にその隣接ノードについて、最小のインデックスをもつ次の未検出の隣接ノードを検査します。隣接ノードがすべて訪問済みのノードを検出するまで、検索が継続されます。この時点で検索は、未検出の隣接ノードをもち、以前検出した最も近いノードまで経路を戻ります。開始ノードから到達可能なすべてのノードが訪問されるまで、このプロセスが継続されます。
この (再帰) アルゴリズムは、疑似コードで次のように記述できます。
Event startnode(S) Call DFS(S) function DFS(C) Event discovernode(C) FOR edge E from outgoing edges of node C, connecting to node N Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E) (depending on the state of node N) IF event was edgetonew Call DFS(N) END END Event finishnode(C) END
dfsearch
は、新しいノードが検出された時点、あるノードから出るすべてのエッジが訪問された時点など、アルゴリズム内での異なるイベントを表すフラグを返すことができます。イベントのフラグを次の表に示します。
イベントのフラグ | イベントの説明 |
---|---|
'discovernode' | 新しいノードが検出されました。 |
'finishnode' | ノードから出るすべてのエッジが訪問されました。 |
'startnode' | このフラグは検索の開始ノードを示します。 |
'edgetonew' | エッジは未検出のノードに連結しています。 |
'edgetodiscovered' | エッジは以前検出したノードに連結しています。 |
'edgetofinished' | エッジは終了ノードに連結しています。 |
詳細は、events
の入力引数の説明を参照してください。
メモ
開始ノードから到達できないノードが入力グラフに含まれている場合、'Restart'
オプションにより検索でグラフ内の各ノードを訪問できます。この場合、'startnode'
イベントは検索が再開されるたびに開始ノードを示します。
拡張機能
バージョン履歴
R2015b で導入