3

G = (V,E)接続された無向グラフに対して深さ優先検索 (DFS) アルゴリズムを実行すると、スパニング ツリーが提供されます。グラフで DFS を実行しているときに、次数が 1 より大きい頂点に到達すると、つまり、複数のエッジが接続されている場合、続行するエッジをランダムに選択します。続行するエッジ (または頂点) を選択するオプションで、DFS を使用して特定のグラフのすべてのスパニング ツリーを実際に作成できるかどうかを知りたいですか?

4

2 に答える 2

2

コメントで、スパニング ツリーを指定すると、同じツリーを出力する DFS が必要だと述べたので、これは問題になりません。

必要なスパニング ツリーと隣接リストの形式のグラフがあり、指定されたスパニング ツリーにエッジが存在するかどうかに応じて true または false を返すメソッド edge_exists(u,v) があるとします。

explore(node):
   visited[node] = 1;
   for v in node.neighbors:
       if edge_exists(node, v) && !visited[v]:
           v.p = node
           explore(v)

ところで、スパニング ツリーがあるので、訪問数をカウントする必要はないと思います。

スパニング ツリーをプログラムで出力するということは、すべてのスパニング ツリーを出力するグラフが与えられたということです。これを行う方法がわかりません。

于 2013-07-12T08:30:39.943 に答える