深度优先遍历

借助栈和集合实现树和图的深度优先遍历, 每次从栈中取出一个节点 A , 遍历与节点 A 相邻的后续节点 Bn , 若集合中没有该后续 Bn 则将节点 A 放回栈中, 并将后续节点 Bn 放入栈和集合中, 输出后续节点 Bn . 每遍历完一个后续节点就跳出当前循环, 避免出现横向遍历 ( 如下图, 可能会产生 2, 3, 4 的错误输出 ).

以上图为例, 图的节点定义及整体结构见上一篇博客

Java

public class DFS {
    public static void dfs(GraphNode node) {
        if (node == null) return;

        Stack<GraphNode> stack = new Stack<>();
        HashSet<GraphNode> set = new HashSet<>();
        stack.push(node);
        set.add(node);
        System.out.print(node.value + " ");
        while (!stack.isEmpty()) {
            GraphNode cur = stack.pop();
            for (GraphNode next : cur.nexts) {
                if (!set.contains(next)) {
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    System.out.print(next.value + " ");
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        Integer[][] nodes = {
                {1, 1, 2},
                {1, 1, 3},
                {1, 1, 4},
                {1, 2, 3},
                {1, 2, 7},
                {1, 3, 5},
                {1, 4, 6},
                {1, 7, 3}
        };
        Graph graph = GraphBuilder.createGraph(nodes);
        dfs(graph.nodes.get(1));
    }
}

1 2 3 5 7 4 6

Python

def dfs(node):
    if not node: return

    ele_stack = []
    ele_set = set()

    ele_stack.append(node)
    ele_set.add(node)

    print(node.value, end=' ')
    while ele_stack:
        current_node = ele_stack.pop()
        for next_node in current_node.nexts:
            if next_node not in ele_set:
                ele_stack.append(current_node)
                ele_stack.append(next_node)
                ele_set.add(next_node)
                print(next_node.value, end=' ')
                break