图（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」表示有多少条边从该顶点指出。

图的表示方式

  1. 邻接矩阵

    设图的顶点数量为n，「邻接矩阵 adjacency matrix」使用一个 n×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

    邻接矩阵具有以下特性。

    • 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
    • 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
    • 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。

  2. 邻接表

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

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

图的遍历

  1. 广度优先遍历 - BFS

    广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。

    算法实现：

    • 将遍历起始顶点 startVet 加入队列，并开启循环。
    • 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
    • 循环步骤 2. ，直到所有顶点被访问完毕后结束。

    备注：为了防止重复遍历顶点，我们需要借助一个哈希表 visited 来记录哪些节点已被访问。当然，具体用什么结构来记录节点是否被访问取决于具体问题。

  2. 深度优先遍历 - DFS

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

实际应用

  1. 133. 克隆图

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    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;
        }
    }

  2. 207. 课程表

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    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;
        }
    }