图的表示方法

邻接表法
邻接矩阵法

alt

邻接表法：

A：C、D
B：C
C：A、B、D
D：A、C

邻接矩阵法：

alt

图的遍历

广度优先遍历（BFS）
深度优先遍历（DFS）

BFS

public void bsf(Node node){
    Deque<Node> deque = new ArrayDeque<>();
    Set<Node> set = new HashSet<>();
    deque.offer(node);
    set.add(node);
    while(!deque.isEmpty()){
        Node temp = deque.poll();
        System.out.println("操作" + temp);
        for(Node n : temp.next){
            if(!set.contains(n)){
                deque.offer(n);
                set.add(n);
            }
        }
    }
}

DFS

public void dfs(Node node){
    Deque<Node> deque = new ArrayDeque<>();
    Set<Node> set = new HashSet<>();
    deque.push(node);
    set.add(node);
    while(!deque.isEmpty()){
        Node temp = deque.pop();
        System.out.println("操作" + temp);
        for(Node n : temp.next){
            if(!set.contains(n)){
                deque.push(temp);
                deque.push(n);
                set.add(n);
                break;
            }
        }
    }
}

图的常见算法类型

有向图 -- > 拓扑排序

核心：在于寻找入度为 0 的节点，删除与之相邻的边；之后继续寻找入度为 0 的节点。
应用：可以检测 Spring循环依赖的过程的算法 (美团二面被问到)
时间复杂度/空间复杂度：O（n + m）
207. 课程表

无向图 -- > 最小生成树

kruskal 算法，时间复杂度：O(eloge)
Prim 算法，时间复杂度：O(n ^ 2)
kruskal 与 Prim

路径最小

Dijkstra 算法，时间复杂度：O(n ^ 2)
Floyed 算法，时间复杂度：O(n ^ 3)
Bellman-Ford 算法，时间复杂度：O(VE)
Dijkstra、Floyed、Bellman-Ford