поиск самого длинного пути в графе

Вы можете использовать defaultdict для создания своего « defaultdict » из списка ребер / путей:

 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 .

Из этого вы можете использовать алгоритм, такой как поиск по глубине или поиск по ширине, чтобы обнаружить все пути на графике.

В следующем коде я использовал 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) 

Вывод:

 Все пути:
    [('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11 '), (' 1 ',' 11 ',' 4 '), (' 1 ',' 11 ',' 4 ',' 2 ')]
 Самые длинные пути:
    ('1', '2', '4', '11')
    ('1', '11', '4', '2')
 Самая длинная длина пути:
    4

Обратите внимание, что «начальная точка» вашего поиска определяется вторым аргументом функции DFS , в этом случае это « '1' .

---

Обновление: как обсуждалось в комментариях, приведенный выше код предполагает, что у вас есть исходная точка (в частности, код использует узел с меткой '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))) 

).

Вот мой код, который работает для ввода в примере, но если я немного подкорректирую вход, код не сможет указать правильное количество городов.

 def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) #had to do this for the key error that i was getting if the start doesn't #have any val. if isinstance(start,str) and start not in graph.keys(): pass else: for next in set(graph[start]) - visited: dfs(graph, next, visited) return visited def maxno_city(input1): totalcities = [] max_nocity = 0 routedic = {} #dup = [] rou = [] for cities in input1: cities = cities.split('#') totalcities.append(cities) print (totalcities) for i in totalcities: if i[0] in routedic.keys(): routedic[i[0]].append(i[1]) else: routedic.update({i[0]:[i[1]]}) print(routedic) keys = routedic.keys() newkeys = [] for i in keys: newkeys.append(i) print (newkeys) newkeys.sort() print (newkeys) expath = dfs(routedic,newkeys[0]) return(len(expath)) 

Выход для указанного выше ввода – 4 и я получаю 4 но если вход изменен на что-то вроде этого: ['1#2','2#3','1#11','3#11','4#11','4#5','5#6','5#7','6#7','4#12','8#12','9#12','8#10','9#10',8#9] Мой код не работает.

Спасибо, LearningNinja: D