python - 在图中找到最长的路径

Question

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

例如: 如果给定的路线是 [['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']] 那么连接的最大城市数将为 4限制是我不能访问我已经访问过的城市。

我需要想法，比如如何进步。

目前，我的想法是，如果我能够创建一个字典，以城市为键，并将它连接到多少个其他城市作为其值，我就会接近解决方案(我希望如此)。例如:我的字典将是 {'1': ['2', '11'], '4': ['11'], '2': ['4']}对于上面给定的输入。如果我遗漏了任何内容，我希望获得进一步的帮助和指导。

Answer 1

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

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.

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

Note, the "starting point" of your search is specified by the second argument to the DFS function, in this case, it's '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)

Changing the line

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

).