1. ホーム
  2. algorithm

[解決済み] DFS-Forest Componentとは?

2022-02-06 17:41:30

質問事項

Depth First Searchの仕組みや実装方法は分かっているのですが、教科書にDFS-Forest Componentと書かれているのをよく見かけるのですが、その意味がよく分かりません。グラフのコンポーネントとは、他のコンポーネントから切り離された部分グラフであることは知っています。では、DFS-Forestコンポーネントとは何なのでしょうか?

どのように解決するのですか?

によると このエジンバラ大学の論文 :

<ブロッククオート

ある頂点vから始まるDFSは、グラフを探索するために vから到達可能なすべての頂点と、すべての頂点を含むツリーです。 を使用する。この木をDFS ツリーです。グラフ全体を探索する完全なDFS(グラフの一部分だけでなく ある頂点vから到達可能な木の集合体、または、その集合体を構築します。 DFSフォレストと呼ばれる。