我一直在嘗試對圖表的路徑進行排序。
例如，我在 python 中有以下串列。
graph = [
[4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [1, 0], [0, 2], [4, 1]
]
結果必須是，
graph = [
[0, 2], [2, 5], [5, 7], [7, 3], [3, 8], [8, 6], [6, 4], [4, 1], [1, 0]
]
0 -> 2 -> 5 -> 7 -> 3 -> 8 -> 6 -> 4 -> 1 -> 0
前提是路徑以初始值為零 (0) 的邊開始，以最后一個元素也為零的邊結束。
這是另一個例子：
graph = [
[0, 4], [4, 6], [8, 3], [3, 7], [5, 2], [2, 1], [1, 0], [7, 6], [5, 8]
]
結果需要是：
graph = [
[0, 1], [1, 2], [2, 5], [5, 8], [8, 3], [3, 7], [7, 6], [6, 4], [4, 0]
]
0 -> 1 -> 2 -> 5 -> 8 -> 3 -> 7 -> 6 -> 4 -> 0
方向無所謂。
我從這段代碼開始。
def sort_graph(graph):
sorted_graph = []
for edge in graph:
if edge[0] == 0:
sorted_graph.append(edge)
for edge in graph:
if edge[0] != 0:
sorted_graph.append(edge)
return sorted_graph
但我不知道從這里去哪里。
uj5u.com熱心網友回復：
對于回圈中的每個節點，跟蹤它的兩個鄰居。然后，您可以遍歷這些鄰居以生成節點的排序。一旦你到達一個節點，兩個鄰居都已經被訪問過，你就完成了。
neighbors = {}
for fst, snd in graph:
neighbors.setdefault(fst, []).append(snd)
neighbors.setdefault(snd, []).append(fst)
seen_both_neighbors = False
current = 0
path = []
seen = set()
while not seen_both_neighbors:
path.append(current)
fst, snd = neighbors[current]
if fst not in seen:
seen.add(current)
current = fst
elif snd not in seen:
seen.add(current)
current = snd
else:
seen_both_neighbors = True
result = list(map(list, zip(path, path[1:] [path[0]])))
print(result)
對于您的兩個示例，這都會產生正確的排序答案。
uj5u.com熱心網友回復：
這是一個有趣的問題要解決！這是我對這種方法的想法：
- 查找所有對（向前和向后）
- 創建查找表以輕松導航它們
- 從 0 開始，遍歷并移除你已經訪問過的節點
from itertools import chain
import random
graph = [
[4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [1, 0], [0, 2], [4, 1]
]
# find all pairs independent of their direction
all_pairs = [*graph, *([t, f] for f, t in graph)]
# find all nodes
nodes = set(chain(*all_pairs))
# create a lookup dictionary for each point to show where you could go to
lookup = {node: {to_ for (from_, to_) in all_pairs if from_ == node} for node in nodes}
# simple solution - take a random path
from_ = 0
to_ = None
sorted_graph = []
while to_ != 0:
# select a random next point
to_ = random.choice(list(lookup[from_]))
# make sure to delete it so it doesn't get used again
lookup[from_].remove(to_)
lookup[to_].remove(from_)
# add to output
sorted_graph.append((from_, to_))
# tick one step forward
from_ = to_
print(sorted_graph)
uj5u.com熱心網友回復：
如果您不受依賴關系的限制，請networkx使用一種查找回圈的方法。
import networkx as nx
graph = [
[4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [1, 0], [0, 2], [4, 1]
]
# build a graph object
G = nx.Graph(graph)
# find a cycle starting from node 0
nx.find_cycle(G, source=0)
# [(0, 1), (1, 4), (4, 6), (6, 8), (8, 3), (3, 7), (7, 5), (5, 2), (2, 0)]
來源
uj5u.com熱心網友回復：
您還可以實作回圈，如下所示：
def cycle(vec):
result = [vec[0]]
s = vec[1:]
index = 0
while s:
if result[-1][0] == 0:
start = index
for i,v in enumerate(s):
if result[-1][1] in v:
del s[i]
result.append(v if v[0] == result[-1][1] else v[::-1])
break
index = 1
return result[start:] result[:start]
cycle(graph)
[[0, 1], [1, 4], [4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [2, 0]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/477048.html
標籤：Python python-3.x 列表