python实现图的遍历（递归和非递归）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python实现图的遍历（递归和非递归），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1697字，纯文字阅读大概需要3分钟。

内容图文

class graph:
    def __init__(self,value):
        self.value=value
        self.neighbors=None


# 图的广度优先遍历
# 1.利用队列实现
# 2.从源节点开始依次按照宽度进队列，然后弹出
# 3.每弹出一个节点，就把该节点所有没有进过队列的邻接点放入队列
# 4.直到队列变空
from queue import Queue
def bfs(node):
    if node is None:
        return
    queue = Queue()
    nodeSet = set()
    queue.put(node)
    nodeSet.add(node)
    while not queue.empty():
        cur = queue.get()               # 弹出元素
        print(cur.value)                # 打印元素值
        for next in cur.neighbors:          # 遍历元素的邻接节点
            if next not in nodeSet:     # 若邻接节点没有入过队，加入队列并登记
                nodeSet.add(next)
                queue.put(next)



# 图的深度优先遍历(非递归)
# 1.利用栈实现
# 2.从源节点开始把节点按照深度放入栈，然后弹出
# 3.每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
# 4.直到栈变空
def dfs(node):
    if node is None:
        return
    nodeSet = set()
    stack = []
    print(node.value)
    nodeSet.add(node)
    stack.append(node)
    while len(stack) > 0:
        cur = stack.pop()               # 弹出最近入栈的节点
        for next in cur.neighbors:         # 遍历该节点的邻接节点
            if next not in nodeSet:    # 如果邻接节点不重复
                stack.append(cur)       # 把节点压入
                stack.append(next)      # 把邻接节点压入
                nodeSet.add(next)           # 登记节点
                print(next.value)       # 打印节点值
                break                   # 退出，保持深度优先

def dfs1(node,nodeset):#递归深度优先遍历
    if node is None:
        return
    print(node.value)
    nodeset.add(node)
    for next in node.neighbors:
        if next not in nodeset:
            dfs1(next, nodeset)


node5=graph(5)
node4=graph(4)
node3=graph(3)
node2=graph(2)
node1=graph(1)
nodeset=set()
node4.neighbors=[node3,node2,node1]
node3.neighbors=[node4]
node2.neighbors=[node4,node5]
node1.neighbors=[node4]
node5.neighbors=[node2]

dfs1(node4,nodeset)
dfs(node4)
bfs(node4)

内容总结

以上是互联网集市为您收集整理的python实现图的遍历（递归和非递归）全部内容，希望文章能够帮你解决python实现图的遍历（递归和非递归）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端