实现常用数据结构(图)——遍历

图的遍历可以分为深度优先遍历(dfs) 和 宽度优先遍历(bfs)

由于图可能会有回路, 因此在遍历过程中可能会存在多次遍历同一个点的情况, 因此在深度优先遍历时, 可以使用一个 mark 集合标记当前节点是否访问过.

DFS

在进行深度优先遍历时, 会将当前路径走到尽头再返回去搜索其他路径, 走到尽头的含义是没有下一个未访问的点. 因此我们一般使用函数的递归调用或使用栈数据结构来保存每次的状态.

由于使用哪种存储形式和遍历的写法没有太大区别, 只是取出下一条路径的方式有些许不同 , 在此仅使用 Python 代码演示遍历过程, 取出下一个节点的过程使用函数 getNextNodes(self, node:Node)->List[Node]

以下是递归版本:

def DFS(self, node: Node):
    # 访问当前节点
    visit(node)
    self.mark[node] = True
    nextNodes = self.getNextNodes(node)
    for nextNode in nextNodes:
        # 如果不不在集合中, 说明未访问过
        if nextNode not in self.mark:
            DFS(nextNode)

以下是非递归版本:

def DFS(self, node: Node):
    stack = []
    stack.append(node)
    while len(stack) != 0:
        # 访问当前节点
        indexNode = stack.pop()
        visit(indexNode)
        self.mark[node] = True
        nextNodes = self.getNextNodes(indexNode)
        for nextNode in nextNodes:
            # 如果不不在集合中, 说明未访问过
            if nextNode not in self.mark:
                stack.append(nextNode)

BFS

在进行宽度优先遍历时, 会将当前节点的所有下一个节点遍历完后, 再走到下一层的节点. 因此我们一般使用队列数据结构来保存每次的状态.

由于使用哪种存储形式和遍历的写法没有太大区别, 只是取出下一条路径的方式有些许不同 , 在此仅使用 Python 代码演示遍历过程, 取出下一个节点的过程使用函数 getNextNodes(self, node:Node)->List[Node]

由于使用 Python 自身的 list 来模拟队列要么时间浪费, 要么空间浪费. 于是我使用了 collections 的 deque 高效队列来实现.

from collections import deque


def BFS(self, node: Node):
    queue = deque()
    queue.appendleft(node)
    while len(queue) != 0:
        # 访问当前节点
        indexNode = queue.pop()
        visit(indexNode)
        self.mark[node] = True
        nextNodes = self.getNextNodes(indexNode)
        for nextNode in nextNodes:
            # 如果不不在集合中, 说明未访问过
            if nextNode not in self.mark:
                queue.appendleft(nextNode)