使用python编写广度优先搜索和递归和非递归深度优先搜索

# 图的各种基础遍历，广度优先搜索，深度优先搜索的递归和非递归方式
import queue as que


class Graph:
    def __init__(self):     # 初始化图数据,这个图是一个具有代表性的不连通图
        self.graph_num = 2
        self.names = [
            ['北京', '上海', '城都'],
            ['城市0', '城市1', '城市2', '城市3', '城市4', '城市5', '城市6'],
        ],
        self.edges = [
            [
                [0, 1, 0],
                [0, 0, 1],
                [1, 0, 0],
            ],
            [
                [0, 1, 1, 1, 0, 0, 0],
                [0, 0, 0, 1, 1, 0, 0],
                [1, 0, 0, 0, 0, 1, 0],
                [0, 0, 1, 0, 1, 1, 1],
                [0, 0, 0, 0, 0, 0, 1],
                [0, 0, 0, 0, 0, 0, 0],
                [1, 0, 0, 0, 0, 1, 0],
            ]
        ]

    def bst(self):  # 广度优先搜索
        for i in range(self.graph_num):
            print('开始遍历图上第{}个不相连的小图：'.format(i))
            print('........................................')
            # print(self.edges[i])
            self.bst_son(self.edges[i])

    @staticmethod
    def bst_son(edges):   # 具体每一个广度优先搜索的具体实现
        length = len(edges)
        looked = [0] * length  # 记录遍历过的节点
        q = que.Queue()
        # 将第一个点加入到队列中去遍历
        start = 0
        q.put(start)
        looked[start] = 1  # 将点标记为已经走过了

        while q.empty() is False:
            i = q.get()

            print('当前正站在{}顶点位置'.format(i))
            for j in range(length):
                # print('...', looked[j], edges[i][j])
                # 节点需要是未看过的，并且是能往下面走的
                if looked[j] == 0 and edges[i][j] == 1:
                    print('当前走过的路径：{}->{}'.format(i, j))
                    q.put(j)
                    looked[j] = 1   # 标记当前节点已经看过了

    # 深度优先搜索
    def dst(self):
        for i in range(self.graph_num):
            print('开始遍历图上第{}个不相连的小图：'.format(i))
            print('........................................')
            # print(self.edges[i])
            edges = self.edges[i]
            length = len(edges)
            looked = [0] * length  # 记录遍历过的节点
            current_node = 0
            looked[current_node] = 1  # 标记当前节点已经走过了
            self.dst_son(edges, looked, current_node, length)

    def dst_son(self, edges, looked, current_node, length):
        print('当前站在{}顶点上'.format(current_node))
        for i in range(length):
            if looked[i] == 0 and edges[current_node][i] == 1:
                print('当前走过的路径：{}->{}'.format(current_node, i))
                looked[i] = 1   # 标记这个节点已经走过了
                self.dst_son(edges, looked, i, length)

    def dst_no_re(self):
        for i in range(self.graph_num):
            print('开始遍历图上第{}个不相连的小图：'.format(i))
            print('........................................')
            # print(self.edges[i])
            self.dst_no_re_son(self.edges[i])

    @staticmethod
    def dst_no_re_son(edges):
        length = len(edges)
        start = 0
        looked = [0] * length   # 标记看过的节点

        stack = que.LifoQueue(length)
        stack.put(start)
        looked[start] = 1

        while stack.empty() is False:
            current_node = stack.get()
            print('当前站在{}顶点上'.format(current_node))

            for j in range(length):
                if looked[j] == 0 and edges[current_node][j] == 1:
                    print('当前走过的路径：{}->{}'.format(current_node, j))
                    looked[j] = 1
                    stack.put(current_node)
                    stack.put(j)
                    break       # break 和 栈是非递归深度优先搜索产生的关键


def main():
    g = Graph()
    print()
    print('广度优先搜索：^^^^^^^^^^^^^^^^^^^^^^^')
    g.bst()

    print()
    print('深度优先搜索递归的形式：^^^^^^^^^^^^^^^^^^^^^^^')
    g.dst()

    print()
    print('深度优先搜索的非递归形式：^^^^^^^^^^^^^^^^^^^^^^^')
    g.dst_no_re()

    print('遍历结束')


if __name__ == '__main__':
    main()