图的遍历

Graph.java

public class Graph {
    // 节点数目
    int size;
    // 保存顶点信息
    String[] nodes;
    // 保存边的信息
    int[][] edges;

    /**
     *    A B C D E F G
     *  A 0 0 1 1 0 1 0
     *  B 0 0 1 0 0 0 0
     *  C 1 1 0 1 0 0 0
     *  D 1 0 1 0 0 0 0
     *  E 0 0 0 0 0 0 1
     *  F 1 0 0 0 0 0 1
     *  G 0 0 0 0 1 1 0
     */
    public Graph() {
        nodes = new String[]{"A", "B", "C", "D", "E", "F", "G"};
        size = nodes.length;

        // 这里初始化的方法更易读，推荐
        final int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6;
        edges = new int[size][size];

        edges[A][C] = 1;
        edges[A][D] = 1;
        edges[A][F] = 1;
        edges[B][C] = 1;
        edges[C][A] = 1;
        edges[C][D] = 1;
        edges[C][B] = 1;
        edges[D][A] = 1;
        edges[D][C] = 1;
        edges[E][G] = 1;
        edges[F][A] = 1;
        edges[F][G] = 1;
        edges[G][F] = 1;
        edges[G][E] = 1;
    }
}

GraphCover.java

import java.util.ArrayList;
import java.util.List;

public class GraphCover extends Graph {
    private int[] visit = new int[size];

    /**
     * 深度优先遍历  Deep First Search
     * 一条路走到黑，不撞南墙不回头
     * @param start
     */
    public void dfs(int start) {
        visit[start] = 1;
        System.out.println("visit to: " + nodes[start]);

        for (int i = 0; i < size; i++) {
            if (edges[start][i] == 1 && visit[i] == 0) {
                dfs(i);
            }
        }
    }

    /**
     * 广度优先遍历  Breath First Search
     * 借助List实现
     */
    public void bfs(List<Integer> tmp_nodes) {
        List<Integer> lastNodes = new ArrayList<>();

        for (int node : tmp_nodes) {
            visit[node] = 1;
            System.out.println("visit to: " + this.nodes[node]);

            for (int i = 0; i < size; i++) {
                if (edges[node][i] == 1 && visit[i] == 0) {
                    visit[i] = 1;
                    lastNodes.add(i);
//                    System.out.println("add lastNode: " + nodes[i]);
                }
            }
        }

        if (lastNodes.size() > 0) {
            bfs(lastNodes);
        }
    }

    /**
     * 借助数组实现
     */
    public void bfs2(int start) {
        queue[0] = start;
        visit[start] = 1;
        breathFirst(0, 0);
    }

    private int[] queue = new int[size];
    private void breathFirst(int front, int tail) {
        int last = tail;

        for (int index = front; index <= tail; index++) {
            int node = queue[index];

            System.out.println("visit to:" + nodes[node]);
            for (int i = 0; i < size; i++) {
                if (edges[node][i] == 1 && visit[i] == 0) {
                    visit[i] = 1;
                    queue[++last] = i;
                }
            }
        }

        if (last > tail) {
            breathFirst(tail + 1, last);
        }
    }
}