时间戳

首页 > 解决方案 > 使用迭代方法从 Python 中的起始节点到达图中的目标节点

python - 使用迭代方法从 Python 中的起始节点到达图中的目标节点

问题描述

我有以下无向图，其中我试图通过所有可用路径5从节点开始到达节点目标节点0，而不仅仅是单个或最短的路径。

该图是这样的字典：

graph = {   "0" : ["2", "1"],
            "2" : ["0", "3", "4"],
            "3" : ["2"],
            "1" : ["0", "5"],
            "4" : ["2", "5"],
            "5" : ["1", "4"]
        }

在此处输入图像描述

我的方法是从起始节点开始，然后遍历每个邻居，然后遍历他们的邻居，直到到达目的地。

但是，我面临的问题是，我无法将 for 循环中的主要迭代实时更改为新的迭代（不可能，强烈不推荐）。

例如，如果我开始在 和 的邻居中循环0，我最初会循环，然后我会在和 之间循环，因为它们是 的邻居，但是，我不能在 for 循环中将其更改为iterative 仍将保留而不是成为。此外，需要以在遍历节点和节点及其邻居之后的方式保持引用，第一个迭代器中的第二个节点应该与它的邻居一起遍历，在这种情况下。21[2, 1]342[2, 1][3, 4][2, 1]34[5]1[1]

标签： pythongraph

解决方案

您可以使用包含要探索的下一个节点列表和到达它们的路径的堆栈结构来迭代地执行此操作。

例如：

def findPath(graph, origin,target):
    stack  = [(origin,[origin])] # Start from origin
    seen   = {origin}            # Track where you've been so far
    while stack:
        node, path = stack.pop(0)                  # BFS (use pop(-1) for DFS)
        for nextNode in graph[node]:               # Go through neighbours
            if nextNode in seen: continue          #    not seen yet
            nextPath = path + [nextNode]           # Record path to get there
            if nextNode == target: return nextPath # Arrived!
            seen.add(nextNode)                     # Avoid returning here
            stack.append( (nextNode,nextPath) )    # Stack for more exploration
    return [] # no path to target

输出：

graph = {   "0" : ["2", "1"],
            "2" : ["0", "3", "4"],
            "3" : ["2"],
            "1" : ["0", "5"],
            "4" : ["2", "5"],
            "5" : ["1", "4"]
        }
print(findPath(graph,"0","5"))
['0', '1', '5']

print(findPath(graph,"3","5"))
['3', '2', '4', '5']

print(findPath(graph,"1","3"))
['1', '0', '2', '3']

BFS（广度优先搜索）将找到最短路径。DFS（深度优先搜索）会消耗更少的内存，但可能找不到最佳路径。

要获得所有可能的路径，您可以将此函数转换为生成器，但是您不能使用“seen”优化，因为它会使到达同一节点的多个部分路径短路。在这种情况下，您应该使用 DFS，因为无论如何您都将探索所有路径，并且 DFS 的内存效率会更高。

def findPaths(graph, origin,target):
    stack  = [(origin,[origin])] # Start from origin
    while stack:
        node, path = stack.pop(-1)                 # DFS (use pop(0) for BFS)
        for nextNode in graph[node]:               # Go through neighbours
            if nextNode in path: continue          # don't loop inside paths 
            nextPath = path + [nextNode]           # Record path to get there
            if nextNode == target:
                yield nextPath                     # Return this path, 
                continue                           #   continue with others
            stack.append( (nextNode,nextPath) )    # Stack for more exploration

输出：

graph = {   "0" : ["2", "1"],
            "2" : ["0", "3", "4"],
            "3" : ["2"],
            "1" : ["0", "5"],
            "4" : ["2", "5"],
            "5" : ["1", "4"]
        }

for path in findPaths(graph,"0","5"): print(path)
['0', '1', '5']
['0', '2', '4', '5']


for path in findPaths(graph,"3","5"): print(path)
['3', '2', '4', '5']
['3', '2', '0', '1', '5']


for path in findPaths(graph,"1","3"): print(path)
['1', '0', '2', '3']
['1', '5', '4', '2', '3']

推荐阅读