图论之深度优先遍历

深度优先遍历

package com.zhang.reflection.面试.算法模版.图.遍历;
import java.util.*;
/**
 * 深度有限遍历，利用栈实现，从源节点开始把节点按照深度放入栈，
 * 然后弹出，没弹出一个节点，把该节点下一个没有进过栈的邻接节点放入栈，直到栈为空。
 */
public class dfs {
    //图
    static class Graph{
        //点集<编号，实际的点>
        public HashMap<Integer, bfs.Node> nodes;
        //边集
        public HashSet<bfs.Edge> edges;
        public Graph(){
            nodes=new HashMap<>();
            edges=new HashSet<>();
        }
    }
    //点
    static class Node{
        //点上的值
        public int value;
        //点的入度
        public int in;
        //点的出度
        public int out;
        //相邻节点集,以该节点为起点
        public ArrayList<Node> nexts;
        //相邻边集，以该节点为起点
        public ArrayList<Edge> edges;
        public Node(int value){
            this.value=value;
            in=0;
            out=0;
            nexts=new ArrayList<>();
            edges=new ArrayList<>();
        }
    }
    //边
    static class Edge{
        //边得权值
        public int weight;
        //边的起点
        public bfs.Node from;
        //边的终点
        public bfs.Node to;
        public Edge(int weight, bfs.Node from, bfs.Node to){
            this.weight=weight;
            this.from=from;
            this.to=to;
        }
    }
    /**
     *         A
     *      /  \  \
     *     B---C---E
     *         \  /
     *          D
     */
    private void dfs(Node node){
        if(node==null){
            return ;
        }
        Deque<Node> stack=new LinkedList<>();
        HashSet<Node> set=new HashSet<>();
        stack.push(node);
        set.add(node);
        //深度优先遍历是一个点进去的时候处理
        System.out.println(node.value);
        while(!stack.isEmpty()){
            Node cur=stack.pop();
            for(Node next:cur.nexts){
                if(!set.contains(next)){
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    //深度优先遍历是一个点进去的时候处理
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }
}