图：图的遍历

图的遍历

1、定义

图的遍历是从图的某一顶点出发，对图中所有顶点访问一次且仅访问一次。

图结构：

public class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

顶点结构：

public 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<>();
    }
}

边结构：

public class Edge {
    public int weight;  //权值
    public Node from;   //有向图中，起始点
    public Node to;     //有向图中，终止点

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }

}

2、深度优先遍历（DFS）（栈）

2.1 基本思想

1. 访问顶点 v；
2. 从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进行深度优先遍历；
3. 重复上述两步，知道图中所有和 v 有路径相通的顶点都被访问到。

2.2 代码实现

public static void dfs(Node node) {
    if (node == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.push(node);
    set.add(node);
    System.out.println(node.value);
    while (!stack.empty()) {
        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;
            }
        }
    }
}

3、广度优先遍历（BFS）（队列）

3.1 基本思想

1. 访问顶点 v；
2. 依次访问 v 的各个为访问邻接点 v₁，v₂，v₃，……，v_k；
3. 分别从 v₁，v₂，v₃，……，v_k 出发一次访问它们未被访问的邻接点，并使 “先被访问顶点的邻接点” 先于 “后被访问顶点的邻接点” 被访问。直至图中所有与顶点 v 有路径相通的顶点都被访问到。

3.2 代码实现

public static void bfs(Node node) {
    if (node == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();    //防止重读
    queue.add(node);
    set.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                queue.add(next);
                set.add(next);
            }
        }
    }
}