Python图遍历算法：深度优先、广度优先

图是解决许多重要数学问题非常有用的数据结构。例子包括计算机网络拓扑或化合物分子结构的分析。它们用于城市交通或路线规划，甚至用于人类语言和语法。所有这些应用程序都面临着遍历图并确保图中的每个节点都被访问的共同挑战。有两种普遍接受的执行此类爬网的方法，如下所述。

深度优先遍历：

也称为深度优先搜索 (DFS)，该算法使用堆栈来记住下一个顶点，以便在任何迭代中出现死胡同时开始搜索。使用 Python 中设置的数据类型实现 DFS 图，因为它们提供了跟踪已访问和未访问节点的功能。

参见以下代码的实现 –

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

Python

运行上面的示例代码，得到以下结果：

a
b
d
e
c

Shell

广度优先遍历

也称为广度-fi搜索（BFS），该算法使用队列来记住，如果任何迭代中发生死锁，则获取下一个顶点来开始搜索。

BFS 使用前面讨论的序列数据结构在 python 中实现。如果继续访问相邻的未访问节点，则继续将其添加到队列中。然后仅显示未访问的节点。如果没有访问下一个相邻节点，则停止程序。

查看以下代码的实现 -

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

Python

运行上面的示例代码，得到以下结果 -

a c b d e