Python 图算法



Python 图算法

Python 图算法详细操作教程

在解决许多重要的数学难题时,图形是非常有用的数据结构。例如计算机网络拓扑或分析化合物的分子结构。它们还用于城市交通或路线规划,甚至还用于人类语言及其语法。所有这些应用程序都有一个共同的挑战,即使用它们的边缘遍历图并确保访问图的所有节点。有两种常见的建立方法可以进行遍历,下面将对此进行介绍。

深度优先遍历:

也称为深度优先搜索(DFS),当任何迭代中出现死角时,该算法都会在深度病房运动中遍历图形,并使用堆栈记住下一个顶点以开始搜索。我们使用设置的数据类型为python中的图形实现DFS,因为它们提供了必需的功能来跟踪已访问和未访问的节点。
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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')

运行结果如下:
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
a b d e c

广度优先遍历

也称为广度优先搜索(BFS),该算法遍历图广度移动,并在任何迭代出现死角时使用队列记住下一个顶点来开始搜索。请访问我们网站上的此链接以了解图表的BFS步骤的详细信息。

我们使用前面讨论的队列数据结构为python中的图形实现BFS。当我们继续访问相邻的未访问节点并将其添加到队列中时。然后,我们仅开始使没有未访问节点的剩余节点出队。当没有下一个相邻节点要访问时,我们将停止程序。
 # Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
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")

运行结果如下:
a c b d e