在图中找到最长的路径 [英] finding longest path in a graph
问题描述
我正在尝试解决一个程序,其中我必须找到给定路线列表所连接的最大城市数。
I am trying to solve a program, where in I have to find the max number of cities connected for a given list of routes.
例如:
,如果给定的路线是 [[''1','2'],['2','4'],['1','11'],['4',' 11']]
,那么连接的最大城市数将为 4
,因为我无法访问我所访问的城市
for eg:
if the given route is [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]
then max cities connected will be 4
constraint is I can't visit a city which I already have visited.
我需要一些想法,例如如何前进。
I need ideas, as in how to progress.
现在,我所拥有的我的想法是,如果我能够以城市为关键词,并以其价值与之联系的其他城市来创建字典,那我就可以找到解决方案了(我希望)。
例如:我的字典将是 {'1':['2','11'],'4':['11'],'2':['4' ]}
用于上述输入。
如果我缺少任何内容,我希望获得进一步的帮助和指导。
For now, What I have thought is if I could be able to create a dictionary with cities as a key and how many other cities its connected to as its value, i get somewhere near to the solution(I hope).
for eg: My dictionary will be {'1': ['2', '11'], '4': ['11'], '2': ['4']}
for the above given input.
I want help to proceed further and guidance if I am missing anything.
推荐答案
您可以使用 defaultdict
创建您的边缘/路径列表中的图形:
You can use a defaultdict
to create your "Graph" from your list of edges/paths:
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
。
Note that I added the edges in both directions, since you're working with an undirected graph. So with the edge (a,b), G[a]
will include b
and G[b]
will include a
.
从此,您可以使用像深度优先搜索或宽度优先搜索,以发现图中的所有路径。
From this, you can use an algorithm like depth-first search or breadth-first search to discover all the paths in the graph.
代码,我使用了DFS:
In the following code, I used 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')]
完整的代码,最后一位显示最长的路径:
So the full code, with the final bit that shows the longest path:
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 '
。
Note, the "starting point" of your search is specified by the second argument to the DFS
function, in this case, it's '1'
.
更新:如评论中所述上面的代码假定您已牢记起点(特别是代码使用标记为'1'
的节点)。
Update: As discussed in the comments the above code assumes you have a starting point in mind (specifically the code uses the node labelled '1'
).
在您没有这样的起点的情况下,更通用的方法是从每个节点开始执行搜索,并以最长的时间进行搜索。
(注意:实际上,您可能比这更聪明)
A more general method, in the case that you have no such starting point, would be to perform the search starting at every node, and take the overall longest. (Note: In reality, you could be smarter than this)
更改路线
all_paths = DFS(G, '1')
到
all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps]
将为您提供 any 两点之间的最长路径。
would give you the longest path between any two points.
(这是一个愚蠢的列表理解,但是它只允许我更新一行。更清楚地说,它等效于以下内容:
(This is a silly list comprehension, but it allows me to update only a single line. Put more clearly, it's equivalent to the following:
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)))
)。
这篇关于在图中找到最长的路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!