Вы можете использовать defaultdict, чтобы создать свой «Graph» из списка ребер/путей:
edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]
G = defaultdict(list)
for (s,t) in edges:
G[s].append(t)
G[t].append(s)
print G.items()
Выход:
[
('1', ['2', '11']),
('11', ['1', '4']),
('2', ['1', '4']),
('4', ['2', '11'])
]
Обратите внимание, что я добавил края в обоих направлениях, так как вы работаете с неориентированным графиком. Таким образом, с краем (a, b), G[a] будет включать b и G[b] будет включать в себя a.
С помощью этого алгоритма можно использовать depth-first search или breadth-first search, чтобы открыть все пути на графике.
В следующем коде, я использовал DFS:
def DFS(G,v,seen=None,path=None):
if seen is None: seen = []
if path is None: path = [v]
seen.append(v)
paths = []
for t in G[v]:
if t not in seen:
t_path = path + [t]
paths.append(tuple(t_path))
paths.extend(DFS(G, t, seen[:], t_path))
return paths
Что вы можете использовать с:
G = defaultdict(list)
for (s,t) in edges:
G[s].append(t)
G[t].append(s)
print DFS(G, '1')
Выход:
[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')]
Так полный код, с окончательным бит, который показывает самый длинный путь:
from collections import defaultdict
def DFS(G,v,seen=None,path=None):
if seen is None: seen = []
if path is None: path = [v]
seen.append(v)
paths = []
for t in G[v]:
if t not in seen:
t_path = path + [t]
paths.append(tuple(t_path))
paths.extend(DFS(G, t, seen[:], t_path))
return paths
# Define graph by edges
edges = [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]
# Build graph dictionary
G = defaultdict(list)
for (s,t) in edges:
G[s].append(t)
G[t].append(s)
# Run DFS, compute metrics
all_paths = DFS(G, '1')
max_len = max(len(p) for p in all_paths)
max_paths = [p for p in all_paths if len(p) == max_len]
# Output
print("All Paths:")
print(all_paths)
print("Longest Paths:")
for p in max_paths: print(" ", p)
print("Longest Path Length:")
print(max_len)
Выход:
All Paths:
[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')]
Longest Paths:
('1', '2', '4', '11')
('1', '11', '4', '2')
Longest Path Length:
4
Обратите внимание, «отправной точкой» вашего поиска задается вторым аргументом функции DFS, в данном случае, это '1'.
Update: Как обсуждалось в комментариях выше код предполагает, что вы имеете отправную точку в виду (в частности, код использует узел помеченный '1').
Более общий метод, если у вас нет такой отправной точки, будет выполнять поиск, начинающийся с с каждым узлом, и занимает наибольшее время. (Примечание: На самом деле, вы могли бы быть умнее, чем это)
Изменение линии
all_paths = DFS(G, '1')
в
all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps]
даст вам самый длинный путь между любые две точки.
(. Это глупо список понимание, но это позволяет мне обновить только одну строку Помещенный более ясно, что это эквивалентно следующему:
all_paths = []
for node in set(G.keys()):
for path in DFS(G, node):
all_paths.append(path)
или
from itertools import chain
all_paths = list(chain.from_iterable(DFS(G, n) for n in set(G)))
).
С точки зрения алгоритмов, вы можете посмотреть в [поиск в глубину] (http://en.wikipedia.org/wiki/Depth-first_search) или [в ширину поиск] (http://en.wikipedia.org/wiki/Breadth-first_search) – jedwards
@jedwards Спасибо. Я просмотрел страницы. Я был бы очень признателен, если бы вы помогли мне с его реализацией или просто уточнили, как его реализовать. – LearningNinja
Самая длинная проблема пути - проблема с NP. См. Http://en.m.wikipedia.org/wiki/Longest_path_problem. Вы можете использовать библиотеку графов или использовать известный алгоритм для ее решения. – Tarik