我正在尝试解决一个问题，需要找出给定路线中连接的城市数量最多的情况。
例如：
如果给定的路线是[['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']]，
那么连接的最大城市数将为4。
约束条件是我不能访问已经访问过的城市。
我需要想法，如何进一步处理。
目前，我想到的是如果我能够创建一个以城市为键、它所连接的其他城市数量为值的字典，就可以接近解决方案（我希望如此）。
例如：对于上述输入，我的字典将是{'1': ['2', '11'], '4': ['11'], '2': ['4']}。
我需要进一步的帮助和指导，如果我漏掉了什么。
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)
输出：
所有路径：
[('1', '2'), ('1', '2', '4'), ('1', '2', '4', '11'), ('1', '11'), ('1', '11', '4'), ('1', '11', '4', '2')]
最长路径：
('1', '2', '4', '11')
('1', '11', '4', '2')
最长路径长度：
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)))
).
G[t].append(s)。 - jedwards这是我的代码，它可以处理示例中的输入，但如果我稍微调整一下输入，代码就无法给出正确的连接城市数量。
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))