9

現在、接続のリストがリストに保存されています。各接続は、2 つのポイントを接続する有向リンクであり、ポイントが複数のポイントにリンクしたり、複数のポイントにリンクされたりすることはありません。例えば：

connections = [ (3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1) ]

生成する必要があります:

ordered = [ [ 4, 6, 5, 3, 7, 8 ], [ 1, 2, 1 ] ]

入力ポイントと接続のリストを受け取り、それ自体を再帰的に呼び出して次のポイントを見つけ、それを成長する順序付きリストに追加するアルゴリズムを使用してこれを実行しようとしました。ただし、正しいポイントから開始しないと (これは同じアルゴリズムを逆に繰り返すだけの問題である必要があります)、接続されていないストランドが複数ある場合にも、私のアルゴリズムは機能しなくなります。

これらの接続を順序付けるための効率的なアルゴリズムを作成する最良の方法は何でしょうか?

4

3 に答える 3

2

このようなもの：

from collections import defaultdict
lis = [ (3, 7), (6, 5), (4, 6), (5, 3), (7, 8), (1, 2), (2, 1) ]
dic = defaultdict(list)

for k,v in lis:
    if v not in dic:
        dic[k].append(v)
    else:
        dic[k].extend([v]+dic[v])
        del dic[v]

for k,v in dic.items():
    for x in v:
        if x in dic and x!=k:
            dic[k].extend(dic[x])
            del dic[x]

print dic
print [[k]+v for k,v in dic.items()]

出力：

defaultdict(<type 'list'>, {2: [1, 2], 4: [6, 5, 3, 7, 8]})
[[2, 1, 2], [4, 6, 5, 3, 7, 8]]
于 2013-05-07T01:20:53.853 に答える
0

おそらく次のようなものでそれを行うことができると思いますO(n)：

ordered = {}

for each connection (s,t):
  if t exists in ordered :
     ordered[s] = [t] + ordered[t]
     del ordered[t]
  else:
     ordered[s] = [t]

# Now merge...
for each ordered (s : [t1, t2, ... tN]):
  ordered[s] = [t1, t2, ... tN] + ordered[tN]
  del ordered[tN]

最後にこのようなものが残りますが、それはかなり簡単に変換できます

ordered = { 
  4 : [6, 5, 3, 7, 8],
  2 : [1, 2]
}
于 2013-05-07T00:54:22.190 に答える