指向グラフが線形の場合は、ノードを順番に返します。そうでなければ失敗します

Question

問題

edges (a, b)のセットを持っています。

エッジ数はノード数 - 1になることが保証されています.1。

私は、シーケンスがグラフ内の all ノードを含むノードaのシーケンスを見つけるアルゴリズムを探しています。 与えられたbのセットが必要なエッジのセットと等しくないため、そのシーケンスが不可能な場合は、スローされるエラーが必要です。

編集：グラフには、任意の数の切断されたコンポーネントがあります。私は明らかに複数の切断されたコンポーネントを持つグラフを線形として考えることはありません。

これまでのアイデア

[n_1, ... n_n]の数が正確に存在するために必要なエッジの数であることを確認していることに注意してください。その結果、ソースまたは宛先を共有するエッジが2つある場合、アルゴリズムは失敗する可能性があります。しかし、私はまだそのシーケンスを得る必要があります。

トポロジーSortは、私の要件を満たす有向グラフの線形順序を返すことを認識しています。ただし、Graphがそれほど線形ではなく、anywaysのように正確に線形ではない場合はまだ失敗します。

私は検証できるかもしれません、そしてトポロジーの種類を実行します。しかし、それは非効率的です。私はまたこの問題の正式なものの名称についてもよくわからないので、単にアルゴリズムを調べるのは難しいです。私はここでいくつかの簡単な接続やトリックが足りないように感じます。

あなたはこれを達成するアルゴリズムを私に提供してもらえますか？私は疑似コードまたはあなたの選択の任意の言語を取ります。

Answer 1

少なくともテストケースに合格するアルゴリズムを考え出した：

let N = set of all nodes
let E = set of all edges

if (|E| != |N|-1) fail

let possibleStartNodes = new set containing all of N
let nexts = new dictionary from node -> node

foreach (prev, next) in E:
  if (next not in possibleStartNodes) fail 
  remove next from possibleStartNodes
  nexts[prev] = next
end foreach

if (|possibleStartNodes| != 1) fail

let currentNode = the one node in possibleStartNodes
let ordering = new list
ordering.push(currentNode)

while (nexts contains value for currentNode) 
  ordering.push(next)
  currentNode = next
end while

return ordering

.

$ O（n）$ は私にとってかなり合理的に見えます。改善する方法はありますか？

編集：私は私が使っている概念のための正しい技術的条件についてのヒントに感謝します

Answer 2

これはあなたが始めたかなり最適なアルゴリズムです。

すべてのエッジを越えて $（A、B）$ 。各エッジについて、すべてのエッジをもう一度進み、数回 $ a $ が表示されます。 $ a $ をディスカバーしたら（これが発生しない場合は拒否）。 $ n_1= a $ 。

すべてのエッジをもう一度上回る、ユニークなエッジ $（n_1、b）$ を探しています $ n_1 $ が表示されます。 $ n_2= b $ 。

すべてのエッジをもう一度上回り、 $（n_2、c）$ を探しています $ n_2 $ < / SPAN>左側に表示されます（そのようなエッジがない場合は、拒否されます）。 $ n_3= c $ 。

続行して、 $ n_4、\ ldots、n_n $ 。

このアルゴリズムは $ o（n ^ 2）$ で実行されます。ハッシュを使用すると、 $ o（n）$ に改善することができるはずです。