在图中找到最长的路径

本文介绍了在图中找到最长的路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试解决一个程序，其中我必须找到给定路线列表所连接的最大城市数。

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)))

）。