チケットのルートを印刷する

Question

今日私は解決できない質問に遭遇しました。

頻繁に旅行者が旅行チケットをすべて徴収します。 チケットには2つの属性、開始旅行名と目的地名のみがあります。デリーからニューヨークへの例。 年末には、旅行者はすべてのチケットをまとめて、1年を通して旅行をマップしようとします。彼の考えられる旅行ルートを判読可能な形式で印刷します。彼は彼の出発地を覚えていない。彼はある場所を何度も訪れることができ、何度も何度も場所を回ることができます。

最初は、グラフを作成する（チケットAからBへの有向枝A→Bの意味）と、実数0（??）のノードからの単純な深さ最初の探索を使用して簡単に解決できると思っていました。しかし、私はそれが解決策を得るための正しい方法ではなく、ランダムな未接続ルートを印刷できることに気付きました。
進める正しい方法を提案してください。

Answer 1

まず、グラフにオイラーのトレイルがあるのか​​、オイラーのサイクルなのかを確認する必要があります。 Aグラフがあればオイラーサイクルを有し、すべての頂点度アウト度で等しい を有し、非ゼロ 度とその頂点の全てが単一の強連結成分に属する。いる場合にのみ向け

同様に、 有向グラフは、 がエッジ - ディスジョントの有向サイクルに分解され、すべての頂点が0でない度合いのあるすべての頂点が単一の強連結成分に属する場合にのみ、オイラー循環を有する。

Aは、グラフはオイラー証跡を有する指向場合にのみ最大で1つの頂点 は（アウト度）がある場合 - （中度）= 1、多くても1つの頂点が（中度） 有し、 - （アウトディグ）= 1であり、すべての他の頂点は等しい度合いであり、 アウトディグリーであり、非ゼロ度を有するその頂点のすべては、基礎をなす無向グラフの単一接続コンポーネントに属する。

グラフにオイラー周期がある場合は、任意のノードからDFSを開始することができ、パスが正しいことを確認できます。

あなたのグラフは、最初の(out-degree) − (in-degree) = 1でノードを検索し、sourceそれを呼び出すと(in-degree) − (out-degree) = 1でノードを検索し、sinkそれを呼び出す、オイラートレイルを持っている場合。 DFSをsourceから開始し、できるだけsinkに行かないようにしてください。これは、ノードsinkと他のいくつかのノードに移動する間に、他のノードに移動し、他のオプションがない場合（正確ではないが単純化する場合）にのみsinkノードを使用するオプションがある場合はいつでも意味します。この方法で、あなたは正しいトレイルで終わることができます。