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')

广度优先遍历

也称为广度优先搜索(BFS),该算法使用队列记住当任何迭代中发生死角时,获取下一个顶点以开始搜索。

我们使用之前讨论的队列数据结构在python中实现BFS。 当继续访问相邻的未访问节点并继续将其添加到队列中。然后,开始只出现没有未访问节点的节点。 当没有下一个相邻节点被访问时,停止程序。

参考以下代码的实现 -

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")
移动端设备除iPad Pro外,其它移动设备仅能阅读基础的文本文字。
建议使用PC或笔记本电脑,浏览器使用Chrome或FireFox进行浏览,以开启左侧互动实验区来提升学习效率,推荐使用的分辨率为1920x1080或更高。
我们坚信最好的学习是参与其中这一理念,并致力成为中文互联网上体验更好的学练一体的IT技术学习交流平台。
您可加QQ群:575806994,一起学习交流技术,反馈网站使用中遇到问题。
内容、课程、广告等相关合作请扫描右侧二维码添加好友。

狐狸教程 Copyright 2021

进入全屏