algorithm - 単向グラフのすべての辺を 1 回だけ歩く

Question

一方向グラフのすべてのエッジを一度だけ歩くことが可能かどうかを教えてくれるアルゴリズムを探しています。アルゴリズムは、任意のノードから開始し、同じエッジを再訪することなくグラフ全体をたどることができなければなりません。

Answer 1

探しているものはオイラー パスと呼ばれ、グラフが必要な条件を満たしている場合、ウィキペディアには、オイラー パスを構築するためのアルゴリズムがいくつか説明されています。

Answer 2

ケーニヒスベルクの7 つの橋は、オイラー パスの典型的な例です。

ウィキペディアの Hierholzer のアルゴリズム:

任意の開始頂点 v を選択し、その頂点から v に戻るまでエッジの軌跡をたどります。v 以外の頂点で立ち往生することはできません。 w w を残して未使用のエッジが存在する必要があります。このように形成されたツアーは閉じたツアーですが、最初のグラフのすべての頂点とエッジをカバーしていない場合があります。

現在のツアーに属しているが、隣接するエッジがツアーの一部ではない頂点 v が存在する限り、v から別のトレイルを開始し、v に戻るまで未使用のエッジをたどり、このようにして形成されたツアーを前の旅行。

双方向リンク リストなどのデータ構造を使用して、各頂点に付随する未使用のエッジのセットを維持し、未使用のエッジを持つ現在のツアーの頂点のリストを維持し、ツアー自体を維持することにより、アルゴリズム (各頂点を出る未使用のエッジの検出、ツアーの新しい開始頂点の検出、頂点を共有する 2 つのツアーの接続) はそれぞれ一定の時間で実行される可能性があるため、アルゴリズム全体では線形時間がかかります。