图（Graph）

「图 graph」是一种非线性数据结构，由「顶点 vertex」和「边 edge」组成。我们可以将图 $G$ 抽象地表示为一组顶点 $V$ 和一组边 $E$ 的集合。

如果将顶点看作节点，将边看作连接各个节点的引用（指针），我们就可以将图看作一种从链表拓展而来的数据结构。

图的分类&术语

根据边是否具有方向，可分为「无向图 undirected graph」和「有向图 directed graph」
根据所有顶点是否连通，可分为「连通图 connected graph」和「非连通图 disconnected graph」
- 对于连通图，从某个顶点出发，可以到达其余任意顶点。
- 对于非连通图，从某个顶点出发，至少有一个顶点无法到达。
还可以为边添加“权重”变量，从而得到「有权图 weighted graph」

图数据结构包含以下常用术语。

「邻接 adjacency」：当两顶点之间存在边相连时，称这两顶点“邻接”。在图 9-4 中，顶点 1 的邻接顶点为顶点 2、3、5。
「路径 path」：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。在图 9-4 中，边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径。
「度 degree」：一个顶点拥有的边数。对于有向图，「入度 in-degree」表示有多少条边指向该顶点，「出度 out-degree」表示有多少条边从该顶点指出。

图的表示方式

邻接矩阵

设图的顶点数量为n，「邻接矩阵 adjacency matrix」使用一个 n×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。
邻接矩阵具有以下特性。
- 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
- 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
- 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。
邻接表

「邻接表 adjacency list」使用 n 个链表来表示图，链表节点表示顶点。第 i 个链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）

邻接表仅存储实际存在的边，而边的总数通常远小于 n² ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

图的遍历

广度优先遍历 - BFS

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。
算法实现：
- 将遍历起始顶点 startVet 加入队列，并开启循环。
- 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
- 循环步骤 2. ，直到所有顶点被访问完毕后结束。
备注：为了防止重复遍历顶点，我们需要借助一个哈希表 visited 来记录哪些节点已被访问。当然，具体用什么结构来记录节点是否被访问取决于具体问题。
深度优先遍历 - DFS

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。

实际应用

133. 克隆图

要将一个图克隆出来，核心是如何遍历图的所有节点。那么也就显而易见有两种方式，即BFS和DFS

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

//DFS
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Node clone = new Node(node.val, new ArrayList<>());
        HashMap<Node, Node> lookup = new HashMap<>();
        lookup.put(node, clone);
        Deque<Node> deque = new LinkedList<>();
        deque.add(node);
        while (!deque.isEmpty()) {
            Node tmp = deque.poll();
            for(Node i: tmp.neighbors){
                if(!lookup.containsKey(i)){
                    deque.offer(i);
                    lookup.put(i,new Node(i.val,new ArrayList<>()));
                }
                lookup.get(tmp).neighbors.add(lookup.get(i));
            }
        }
        return clone;
    }
}

207. 课程表

非常经典的一道题，也从中学到了一个新的知识点-拓扑排序

首先我们对于每个节点，统计其入度，因为入度为0的节点不需要前置课程，所以我们将这些课程先放入队列。然后根据统计的hashmap中的依赖关系，我们将依赖于刚才节点的课程的入度减去一，如果入度变为0（即没有需要的前置课程了）就放入队列，如此循环至队列为空。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            inDegree[prerequisites[i][0]]++;
            List<Integer> tmp = map.getOrDefault(prerequisites[i][1], new ArrayList<>());
            tmp.add(prerequisites[i][0]);
            map.put(prerequisites[i][1], tmp);
        }
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                deque.add(i);
            }
        }
        if (deque.isEmpty()) {
            return false;
        }
        int count = deque.size();
        while (!deque.isEmpty()) {
            if (count == numCourses) {
                return true;
            }
            int node = deque.pop();
            if (map.containsKey(node)) {
                for (int n : map.get(node)) {
                    inDegree[n]--;
                    if (inDegree[n] == 0) {
                        deque.push(n);
                        count++;
                    }
                }
            }
        }
        return count == numCourses;
    }
}