Graph DFS&BFS

Adjacency Matrix

邻接矩阵示例

/*      
        j=0,j=1,j=2,j=3,j=4
   i=0  [1,  0,  1,  0,  1]
   i=1  [0,  0,  0,  0,  0]
   i=2  [1,  0,  1,  0,  1]
   i=3  [0,  0,  0,  0,  0]
   i=4  [1,  0,  1,  0,  1]
 */

public class AdjacencyMatrix {
    // 记录遍历的节点
    private static final List<Integer> result = new ArrayList<>();
    public static List<Integer> traversal(int[][] matrix) {
        // 获取节点个数
        int len = matrix.length;
        // 记录已经被访问的节点
        boolean[] visited = new boolean[len];
        // 从每个节点开始，dfs遍历所有节点
        // 这里为什么要从每个节点dfs遍历
        // 因为会有孤岛，没有联通的节点
        for (int i = 0; i < len; i++) dfs(matrix, i, visited);
        return result;
    }

    /**
     * @param matrix 这里为什么要传递matrix，因为要根据这个matrix查找关联节点
     * @param i 这里的i代表的是顶点vertex
     * @param visited 访问过的节点，防止重复访问形成环
     */
    private static void dfs(int[][] matrix, int i, boolean[] visited) {
        // 访问过了，跳过
        if(visited[i]) return;
        // 没有访问过，加入到list
        result.add(i);
        // 设置为访问过
        visited[i] = true;
        // 从当前节点，纵向扫描数组
        for (int j = 0; j < matrix[i].length; j++) {
            // 如果没有边，跳过
            if(matrix[i][j] != 1) continue;
            // 如果下个节点已经访问过了，跳过
            if(visited[j]) continue;
            dfs(matrix, j, visited);
        }
    }
}

Adjacency List

Basic Data Structure

自定义节点

/**
 * 这里不能用queue，迭代的时候出栈，
 * 就会把图的adjacency List 清空
 * 所以自己构建链表
 */
public class Node<T> {
    T val;
    Node<T> prev;
    Node<T> next;
    public Node(T val){
        this.val = val;
    }
}

自定义链表

public class AdjList<T> {
    // 这里为了方便，自定义链表头尾
    Node<T> head;
    Node<T> tail;
    int size = 0;

    public void addHead(T val) {
        Node<T> newNode = new Node<>(val);
        if(size == 0) {
            head = newNode;
            tail = newNode;
        }else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size ++; // 这里忘了
    }

    public void addLast(T val) {
        Node<T> newNode = new Node<>(val);
        if(size == 0) {
            head = newNode;
            tail = newNode;
        }else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = tail.next;
        }
        size ++; // 这里别忘了
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

图的定义

/**
 * 图
 */
public  class Graph {
    int vertices; // 节点，0...vertices
    AdjList<Integer>[] adjListArray; // 邻接表
    public Graph(int vertices) {
        this.vertices = vertices;
        adjListArray = new AdjList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjListArray[i] = new AdjList<>();
        }
    }

    public void addEdge(int start, int end) {
        if(start > vertices - 1) return;
        adjListArray[start].addLast(end);
    }
}

DFS loop travesal

深度优先遍历，循环方式

/*
 * 0=1->
 * 1=2->3->4->
 * 2=3->
 * 3=4->
 * 4=1->2->
 */
public List<Integer> dfs(Graph g) {
    List<Integer> result = new ArrayList<>(g.vertices);
    boolean[] visited = new boolean[g.vertices];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < g.vertices; i++) {
        // 处理首节点
        deque.offerLast(i);
        // 首节点，这时队列肯定不为空
        while(!deque.isEmpty()) {
            // 出栈
            int val = deque.pollLast();
            // 如果访问过，跳过
            if(visited[val]) continue;
            // 设置为访问过
            visited[val] = true;
            // 加入结果
            result.add(val);
            // 将与当前节点有关联的节点依次放入队列中
            // 下一次判断，肯定是队尾，这里是模拟栈，也就是栈顶
            AdjList<Integer> adjList = g.adjListArray[val];
            Node<Integer> node = adjList.head;
            while(node != null) {
                deque.offerLast(node.val);
                node = node.next;
            }
        }
    }
    return result;
}

DFS recursion traversal

深度优先遍历，递归方式

/*
 * 0=1->
 * 1=2->3->4->
 * 2=3->
 * 3=4->
 * 4=1->2->
 */
public List<Integer> dfs(Graph g) {
    List<Integer> result = new ArrayList<>(g.vertices);
    boolean[] visited = new boolean[g.vertices];
    // 循环每个顶点
    for(int i = 0; i < g.vertices; i++) {
        recursion(g, i, visited, result);
    }
    return result;
}

public void recursion(Graph g,int val, boolean[] visited, List<Integer> result) {
    // 处理当前顶点
    if(visited[val]) return;
    // 访问过的节点一定要跳过
    visited[val] = true;
    result.add(val);
    // 获取当前节点的邻接表(adjacency list)的头结点
    Node<Integer> node = g.adjListArray[val].head;
    // 遍历领接表中的节点
    while(node!= null) {
        recursion(g, node.val,visited, result);
        node = node.next;
    }
}

Graph BFS 图的广度优先遍历

Adjacency Matrix BFS

public class AdjacencyMatrix {
    // 记录遍历的节点
    private static final List<Integer> result = new ArrayList<>();
    public static List<Integer> traversal(int[][] matrix) {
        // 获取节点个数
        int len = matrix.length;
        // 记录已经被访问的节点
        boolean[] visited = new boolean[len];
        /* j==>  0  1  2  3  4
           i=0  [1, 0, 1, 0, 1]
           i=1  [0, 0, 0, 0, 0]
           i=2  [1, 0, 1, 0, 1]
           i=3  [0, 0, 0, 0, 0]
           i=4  [1, 0, 1, 0, 1]
         */
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            // 遍历每一个vertex
            if(visited[i]) continue;
            deque.offerLast(i);// 入队
            visited[i] = true; // 标记已访问
            result.add(i);// 加入结果
            while(!deque.isEmpty()) {
                // 出队
                int val = deque.pollFirst();
                // 遍历关联节点
                for (int j = 0; j < matrix[val].length; j++) {
                    if(matrix[i][j] != 1) continue;
                    if(visited[j]) continue;
                    deque.offerLast(j);
                    visited[j] = true;
                    result.add(j);
                }
            }
        }
        return result;
    }
}

Adjacency List BFS

public List<Integer> bfs(Graph g) {
    List<Integer> result = new ArrayList<>(g.vertices);
    boolean[] visited = new boolean[g.vertices];
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < g.vertices; i++) {
        // 处理首节点
        deque.offerLast(i);
        // 首节点，这时队列肯定不为空
        while(!deque.isEmpty()) {
            // 出栈
            int val = deque.pollFirst();
            // 如果访问过，跳过
            if(visited[val]) continue;
            // 设置为访问过
            visited[val] = true;
            // 加入结果
            result.add(val);
            // 将与当前节点有关联的节点依次放入队列中
            // 下一次判断，肯定是队尾，这里是模拟栈，也就是栈顶
            AdjList<Integer> adjList = g.adjListArray[val];
            Node<Integer> node = adjList.head;
            while(node != null) {
                deque.offerLast(node.val);
                node = node.next;
            }
        }
    }
    return result;
}

Topological Sort

tip

• Directed Acyclic Graph (DAG) 有向无环图
• Active On Vertex (AOV) 顶点表示活动，边表示制约关系
• Active On Edge (AOE)
• 拓扑排序步骤：1. 找到入度为0的节点 2. 删除该节点，加入结果中 3.循环1和2直到没有满-足条件1的节点。
• 判断DAG中的环：1. 进行拓扑排序 2. 判断图的顶点是否都在拓扑排序序列中，都在即无环，否则有环。

private List<Integer> topologicalSort(int vertices, int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int[] inDegrees = new int[vertices];
    // 统计入度
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            if(matrix[i][j] == 1) inDegrees[j] ++;
        }
    }
    // 在队列中的，肯定都是入度为0的vertex
    Queue<Integer> queue = new LinkedList<>();
    // 入度为0的节点入队
    for (int i = 0; i < inDegrees.length; i++) {
       if(inDegrees[i] == 0) queue.offer(i);
    }
    //bfs
    while(!queue.isEmpty()) {
        int i = queue.poll();
        result.add(i);
        for (int j = 0; j < vertices; j++) {
            int edgeFlag = matrix[i][j];
            if(edgeFlag == 1) { // 有边
                // 将关联节点的入度-1
                inDegrees[j] --;
                // 入度为0了，加入队列
                if(inDegrees[j] == 0) queue.offer(j);
            }
        }
    }
    return result;
}