在图中找到最长的路径

Question

我正在尝试解决一个程序,我必须找到给定路径列表的最大连接城市数.

例如:如果给定的路线是[['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']] 最大城市连接将是4 约束是我不能访问我已经访问过的城市.

我需要一些想法,就像如何进步一样.

就目前而言,我所想到的是,如果我能够创建一个以城市为关键字的字典,以及它所连接的其他城市的价值,我会接近解决方案(我希望).例如:我的字典将{'1': ['2', '11'], '4': ['11'], '2': ['4']} 用于上面给出的输入.如果我遗漏任何东西,我希望得到进一步的帮助和指导.

Answer 1

您可以使用a 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)

输出:

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'.

更新: 正如评论中所讨论的,上面的代码假设您有一个起点(特别是代码使用标记的节点'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)))

).