这是图表:
g = {
0: [2, 5, 7],
1: [7],
2: [0, 6],
3: [5, 4],
4: [3, 6, 7],
5: [3, 4, 0],
6: [2, 4],
7: [0, 1, 4]
}
我在 Python 中有以下函数:
def dfs(graph, start, target, visited=None):
if visited is None:
visited = set()
visited.add(start)
for n in (set( graph[start] ) - visited):
dfs(graph, n, target, visited)
return visited
但它返回图中存在的所有顶点,我希望它只返回目标顶点(如果它存在于图中)。 有人可以帮助我吗?
请您参考如下方法:
您想测试是否达到了目标,如果达到了,返回 True。这可以通过对您的代码进行以下编辑来完成:
提高效率的小修改
def dfs(graph, start, target, visited=None):
if visited is None:
visited = set()
visited.add(start)
for n in (set( graph[start] ) - visited):
if n == target:
return True
return dfs(graph, n, target, visited)
return False
编辑:我的算法有误,修复后的版本如下:
def dfs(graph, start, target, visited=None):
if start == target:
return True
if visited is None:
visited = set()
visited.add(start)
found = False
for n in (set( graph[start] ) - visited):
if target == n:
return True
found = dfs(graph, n, target, visited)
return found
