在图中找到最长的路径

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.

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

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.

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

I need ideas, as in how to progress.

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

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.

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

2 个解决方案

#1

You can use a defaultdict to create your "Graph" from your list of edges/paths:

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

Output:

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

请注意,我在两个方向上添加了边,因为您正在使用无向图。因此,对于边(a,b),G [a]将包括b,而G [b]将包括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:

在下面的代码中,我使用了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

Which you can use with:

您可以使用哪些:

G = defaultdict(list)
for (s,t) in edges:
    G[s].append(t)
    G[t].append(s)

print DFS(G, '1')

Output:

[('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)

Output:

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

注意,搜索的“起点”由DFS函数的第二个参数指定,在这种情况下,它是'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').

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

to

all_paths = [p for ps in [DFS(G, n) for n in set(G)] for p in ps]

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)

or

from itertools import chain
all_paths = list(chain.from_iterable(DFS(G, n) for n in set(G)))

).

#2

Here is my code which works for the input in the example but if I tweak the input a little bit, the code fails to give correct number of cities connected.

这是我的代码,它适用于示例中的输入,但如果我稍微调整输入,则代码无法提供正确数量的城市连接。

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

The output for the above given input is 4 and I get 4 but If the input is changed to something like this: ['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] My code fails.

上面给定输入的输出是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]我的代码失败了。

Thanks, LearningNinja :D

谢谢,LearningNinja:D