在解决许多重要的数学挑战时,图形是非常有用的数据结构,如计算机网络拓扑或分析化合物的分子结构,它们还用于城市交通或路线规划中,甚至用于人类语言及其语法中,所有这些应用程序都有一个共同的挑战,即使用它们的边缘遍历图并确保访问图的所有节点,有两种常见的创建方法可以进行此遍历,如下所述。
也称为深度优先搜索(DFS),当任何迭代中出现死角时,该算法都会在深度移动中遍历图形,并使用堆栈记住下一个顶点以开始搜索。 无涯教程使用设置的数据类型为python中的图形实现DFS,因为它们提供了跟踪访问和未访问节点所需的功能。
class graph: def __init__(self,gdict=None): if gdict is None: gdict={} self.gdict=gdict # 检查访问过和未访问过的节点 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')
执行以上代码后,将产生以下输出-
链接:https://www.learnfk.comhttps://www.learnfk.com/python-data-structure/python-graph-algorithms.html
来源:LearnFk无涯教程网
a b d e c
也称为广度优先搜索(BFS),该算法遍历图广度移动,并在任何迭代出现死角时使用队列记住下一个顶点以开始搜索。请访问无涯教程网站上的此链接以了解图表的BFS步骤的详细信息。
使用前面讨论的队列数据结构为python中的图形实现BFS。当继续访问相邻的未访问节点并将其添加到队列中时。然后,仅开始使没有剩下未访问节点的节点出队。当没有下一个相邻节点要访问时将停止程序。
import collections class graph: def __init__(self,gdict=None): if gdict is None: gdict={} self.gdict=gdict def bfs(graph, startnode): # 使用队列跟踪访问过和未访问过的节点 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) #图字典 gdict={ "a" : set(["b","c"]), "b" : set(["a", "d"]), "c" : set(["a", "d"]), "d" : set(["e"]), "e" : set(["a"]) } bfs(gdict, "a")
执行以上代码后,将产生以下输出-
链接:https://www.learnfk.comhttps://www.learnfk.com/python-data-structure/python-graph-algorithms.html
来源:LearnFk无涯教程网
a c b d e
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)