使用字典定义图形并查找路径

Question

>我定义了一个图如下：

adj_matrix = {'1': set('2'),
'2': set('3'),
'3': set(['4', '5']),
'4': set(''),
'5': set('6'),
'6': set('7'),
'7': set('8'),
'8': set(['9', '14']),
'9': set(['10', '11']),
'10': set(''),
'11': set(['12', '13']),
'12': set(''),
'13': set(''),
'14': set('15'),
'15': set('16'),
'16': set('17'),
'17': set(['18', '19']),
'18': set(''),
'19': set('')}

我正在使用以下内容来查找不同节点之间的路径：

def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if start not in graph:
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None

问题是该功能仅适用于114节点。就像当我调用p = find_path(adj_matrix, '3', '14')时，它就像一个魅力，给我['3', '5', '6', '7', '8', '14']答案，但是当我尝试p = find_path(adj_matrix, '3', '15')例如时，它会返回None。任何想法发生了什么以及我如何解决这个问题？

Answer 1

对于错误的情况，当您到达'14'时，可用路由显示为'1'和'5'，而不是'15'。您应该为每个set设置一个列表，以便可以迭代实际值。

adj_matrix = {'1': set(['2']),
'2': set(['3']),
'3': set(['4', '5']),
'4': set(''),
'5': set(['6']),
'6': set(['7']),
'7': set(['8']),
'8': set(['9', '14']),
'9': set(['10', '11']),
'10': set(''),
'11': set(['12', '13']),
'12': set(''),
'13': set(''),
'14': set(['15']),
'15': set(['16']),
'16': set(['17']),
'17': set(['18', '19']),
'18': set(''),
'19': set('')}

使用上面的adj_matrix，它会给出正确的结果。

这是使用我的调试器的函数。您可以看到代码如何从终端流出：

def find_path(graph, start, end, path=[]):
path = path + [start]
print("st:%s, end:%s, path:%s" % (start,end,path))
if start == end:
return path
if start not in graph:
return None
print("available routes: %s" % graph[start])
for node in graph[start]:
if node not in path:
print("next node: %s" % node)
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None

使用错误的adj_matrix，它会给出如下控制台输出：(当涉及到'14'时请仔细观察(

C:UsersrapacDesktopstackoverflow>python adjgraph.py
st:3, end:15, path:['3']
available routes: {'5', '4'}
next node: 5
st:5, end:15, path:['3', '5']
available routes: {'6'}
next node: 6
st:6, end:15, path:['3', '5', '6']
available routes: {'7'}
next node: 7
st:7, end:15, path:['3', '5', '6', '7']
available routes: {'8'}
next node: 8
st:8, end:15, path:['3', '5', '6', '7', '8']
available routes: {'9', '14'}
next node: 9
st:9, end:15, path:['3', '5', '6', '7', '8', '9']
available routes: {'11', '10'}
next node: 11
st:11, end:15, path:['3', '5', '6', '7', '8', '9', '11']
available routes: {'13', '12'}
next node: 13
st:13, end:15, path:['3', '5', '6', '7', '8', '9', '11', '13']
available routes: set()
next node: 12
st:12, end:15, path:['3', '5', '6', '7', '8', '9', '11', '12']
available routes: set()
next node: 10
st:10, end:15, path:['3', '5', '6', '7', '8', '9', '10']
available routes: set()
next node: 14
st:14, end:15, path:['3', '5', '6', '7', '8', '14']
available routes: {'5', '1'} <--- Here it is! We expect '15' here.
next node: 1
st:1, end:15, path:['3', '5', '6', '7', '8', '14', '1']
available routes: {'2'}
next node: 2
st:2, end:15, path:['3', '5', '6', '7', '8', '14', '1', '2']
available routes: {'3'}
next node: 4
st:4, end:15, path:['3', '4']
available routes: set()
None

最后，这是使用正确版本的adj_matrix时的输出：

C:UsersrapacDesktopstackoverflow>python adjgraph.py
st:3, end:15, path:['3']
available routes: {'4', '5'}
next node: 4
st:4, end:15, path:['3', '4']
available routes: set()
next node: 5
st:5, end:15, path:['3', '5']
available routes: {'6'}
next node: 6
st:6, end:15, path:['3', '5', '6']
available routes: {'7'}
next node: 7
st:7, end:15, path:['3', '5', '6', '7']
available routes: {'8'}
next node: 8
st:8, end:15, path:['3', '5', '6', '7', '8']
available routes: {'9', '14'}
next node: 9
st:9, end:15, path:['3', '5', '6', '7', '8', '9']
available routes: {'11', '10'}
next node: 11
st:11, end:15, path:['3', '5', '6', '7', '8', '9', '11']
available routes: {'12', '13'}
next node: 12
st:12, end:15, path:['3', '5', '6', '7', '8', '9', '11', '12']
available routes: set()
next node: 13
st:13, end:15, path:['3', '5', '6', '7', '8', '9', '11', '13']
available routes: set()
next node: 10
st:10, end:15, path:['3', '5', '6', '7', '8', '9', '10']
available routes: set()
next node: 14
st:14, end:15, path:['3', '5', '6', '7', '8', '14']
available routes: {'15'} <-- Now we're good.
next node: 15
st:15, end:15, path:['3', '5', '6', '7', '8', '14', '15']
['3', '5', '6', '7', '8', '14', '15']

现在，代码的行为符合您的预期。希望对您有所帮助。

Answer 2

如果您将输入更改为

adj_matrix = {'1': set('2'),
'2': set('3'),
'3': set(['4', '5']),
'4': set(''),
'5': set('6'),
'6': set('7'),
'7': set('8'),
'8': set(['9', '14']),
'9': set(['10', '11']),
'10': set(''),
'11': set(['12', '13']),
'12': set(''),
'13': set(''),
'14': set(['15']),
'15': set(['16']),
'16': set(['17']),
'17': set(['18', '19']),
'18': set(''),
'19': set('')}

(我刚刚添加了将"15"、"16"和"17"放在列表中。 然后它起作用了。您的问题与以下事实有关：当两位数字单独在集合中时，它们被解释为行for node in graph[start]:中的字符串，然后您循环访问 ['1'， '5']

另请注意，或者您可以简单地使用整数，而每个数字周围都没有引号，我认为这也将解决这个问题。