数据结构图的表示及相关算法&LeetCode题目

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

图的基本概念

顶点（Vertex）与边（Edge）
图的表示：邻接表和邻接矩阵
- 这里可以分为有向图和无向图
- 有权图和无权图
图的遍历：
- DFS
- BFS
- 常见可以解决的问题有：联通分量，Flood Fill，寻路，走迷宫，迷宫生成，无权图的最短路径，环的判断
最小生成树问题（Minimum Spanning Tree）：Prim，Kruskal
最短路径问题（Shortest Path）：Dijkstra，Bellman-Ford
拓扑排序（Topological sorting）

顶点的度

无向图：顶点的度表示以该顶点作为一个端点的边的数目。
有向图：顶点的度分为入度和出度：
- 入度表示以该顶点为终点的入边数目
- 出度是以该顶点为起点的出边数目
- 该顶点的度等于其入度和出度之和

不管是无向图还是有向图，顶点数 n，边数 e 和顶点的度数 D(Vi)有如下关系：
e = 1/2 *(D(v1) + D(v2) + ... + D(vn))

路径、路径长度和回路

路径：比如在无向图 G 中，存在一个顶点序列 Vp，Vi1，Vi2，Vi3 …，Vim，Vq，使得(Vp,Vi1)，(Vi1,Vi2)，…，(Vim,Vq)均属于边集 E(G) ，则称顶点 Vp 到 Vq 存在一条路径。

路径长度：是指一条路径上经过的边的数量。

回路：指一条路径的起点和终点为同一个顶点。

图的存储结构（表示图）

一个图结构

边的集合 Edge lists

To represent an edge, we just have an array of two vertex numbers, or an array of objects containing the vertex numbers of the vertices that the edges are incident on. 无权图可以使用二元组 <Vp, Vq>
If edges have weights, add either a third element to the array or more information to the object, giving the edge's weight. 无权图可以使用三元组 <Vp, Vq, weight>

例如：[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ]

邻接矩阵 Adjacency matrices

使用一个二维数组 adj[][]，如果顶点 i 和顶点 j 之间有边，则 adj[i][j] = 1 or weight

邻接矩阵

邻接表 Adjacency lists

邻接表是图的一种链式存储结构。这种存储结构类似于树的孩子链表。
对于图 G 中每个顶点 Vi，把所有邻接于 Vi 的顶点 Vj 链成一个单链表，这个单链表称为顶点 Vi 的邻接表。

邻接表

图的两种遍历方法

深度优先搜索遍历 DFS

假设初始状态是图中所有顶点都未曾访问过，则可从图 G 中任意一顶点 v 为初始出发点，首先访问出发点 v，并将其标记为已访问过
然后依次从 v 出发搜索v的每个邻接点 w，若 w 未曾访问过，则以 w 作为新的出发点出发，继续进行深度优先遍历，直到图中所有和 v 有路径相通的顶点都被访问到
若此时图中仍有顶点未被访问，则另选一个未曾访问的顶点作为起点，重复上述步骤，直到图中所有顶点都被访问到为止

简单的来说，深度优先搜索包括从一条路径的起始点开始追溯，直到到达最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止。

如果采用邻接矩阵存储，则时间复杂度为 O(n^2)；当采用邻接表时时间复杂度为 O(n + e)。

代码如下：

// 记录每个顶点是否被访问过
boolean visited[] = new boolean[V];

// 从编号为 s 的顶点开始做深度优先遍历
void DFS(int s)
{
    // 首先访问出发点
    visited[s] = true;
    System.out.print(v + " ");

    // 接着依次访问 s 的所有未被访问过的邻接点并均标记为已访问过
    for(each node i which are adjacence of s)
    {
        if (!visited[i]) {
            DFS(i);
        }
    }
}

广度优先搜索遍历 BFS

首先访问出发点 Vi
接着依次访问 Vi 的所有未被访问过的邻接点 Vi1，Vi2，Vi3，…，Vit 并均标记为已访问过
然后再按照 Vi1，Vi2，Vi3，…，Vit 的次序，访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过，依此类推，直到图中所有和初始出发点 Vi 有路径相通的顶点都被访问过为止

简单的来说，广度优先搜索从一个顶点开始，尝试访问尽可能靠近它的顶点。本质上这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层。

如果采用邻接矩阵存储，则时间复杂度为 O(n^2)；当采用邻接表时时间复杂度为 O(n + e)。

代码如下：

// 从编号为 s 的顶点开始做广度优先遍历
void BFS(int s)
{
    // 记录每个顶点是否被访问过
    boolean visited[] = new boolean[V];

    // 使用队列
    LinkedList<Integer> queue = new LinkedList<Integer>();

    // 首先访问出发点
    visited[s] = true;
    queue.add(s);

    while (!queue.isEmpty())
    {
        s = queue.poll();
        System.out.print(s + " ");

        // 接着依次访问 s 的所有未被访问过的邻接点并均标记为已访问过
        for(each node i which are adjacence of s)
        {
            if (!visited[i])
            {
                visited[i] = true;
                queue.add(i);
            }
        }
    }
}

查找最短路径

广度优先搜索对应的最短路径
在执行广度优先搜索时，会自动查找从一个顶点到另一个相邻顶点的最短路径。
例如：要查找从顶点 A 到顶点 D 的最短路径，我们首先会查找从 A 到 D 是否有任何一条单边路径，接着查找两条边的路径，以此类推，这正是广度优先搜索的搜索过程。

LeetCode题目：743. Network Delay Time
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

代码如下：Dijkstra 算法

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        if (times == null || times.length == 0 || times[0].length == 0) {
            return -1;
        }
        
        // 使用邻接矩阵 Adjacency matrices 存储图结构
        int[][] adj = new int[N + 1][N + 1];
        for (int[] arr : adj) {
            Arrays.fill(arr, Integer.MAX_VALUE);
        }
        
        // 有权图
        for (int[] edge : times) {
            adj[edge[0]][edge[1]] = edge[2];
        }

        // res[i] 表示顶点 K 到顶点 i 的时间
        int[] res = new int[N + 1];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[K] = 0;
        
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(K);
        
        while (!queue.isEmpty()) {
            Integer start = queue.poll();
            
            for (int i = 1; i <= N; i++) {
                int weight = adj[start][i];
                
                // DP 动态规划
                if (weight != Integer.MAX_VALUE && res[i] > res[start] + weight) {
                    res[i] = res[start] + weight;
                    queue.offer(i);
                }
            }
        }
        
        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (res[i] == Integer.MAX_VALUE) {
                return -1;
            }
            
            count = Math.max(count, res[i]);
        }
        
        return count;
    }
}

拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。
该序列必须满足下面两个条件：

每个顶点出现且只出现一次
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面

注意：

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说
通常，一个有向无环图可以有一个或多个拓扑排序序列

拓扑排序通常用来“排序”具有依赖关系的任务。它与广度优先搜索BFS类似。
不同的是，拓扑排序算法不会立即输出已访问的顶点，而是访问当前顶点邻接表中的所有相邻顶点，直到这个列表穷尽时，才将当前顶点压入栈中。

基本过程：

从 DAG 图中选择一个没有前驱（即入度为0）的顶点并输出。
从图中删除该顶点和所有以它为起点的有向边。
重复以上步骤直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。

LeetCode题目：207. Course Schedule
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 将 Edge lists 转化为 邻接矩阵 Adjacency matrices
        int[][] adj = new int[numCourses][numCourses];
        int[] indegree = new int[numCourses];
        
        // 构造一个有向图
        for(int[] edge : prerequisites) {
            // p 依赖于 q
            int p = edge[0];
            int q = edge[1];
            
            // 防止重复输入同样的边
            if(adj[q][p] == 0)
                indegree[p]++;
            
            adj[q][p] = 1;
        }
        
        int count = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        
        for(int i = 0; i < numCourses; i++) {
            // 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int i = queue.poll();
            
            count++;
            
            // 从图中删除该顶点和所有以它为起点的有向边
            for(int j = 0; j < numCourses; j++) {
                if(adj[i][j] == 1) {
                    adj[i][j] = 0;
                    indegree[j]--;
                    
                    // 重复以上步骤直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止
                    if(indegree[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }
        
        return count == numCourses;
    }
}

LeetCode题目：210. Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        
        // 将 Edge lists 转化为 邻接矩阵 Adjacency matrices
        int[][] adj = new int[numCourses][numCourses];
        int[] indegree = new int[numCourses];
        
        // 构造一个有向图
        for(int[] edge : prerequisites) {
            // p 依赖于 q
            int p = edge[0];
            int q = edge[1];
            
            // 防止重复输入同样的边
            if(adj[q][p] == 0)
                indegree[p]++;
            
            adj[q][p] = 1;
        }
        
        int count = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        
        for(int i = 0; i < numCourses; i++) {
            // 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int i = queue.poll();
            
            result[count] = i;
            
            count++;
            
            // 从图中删除该顶点和所有以它为起点的有向边
            for(int j = 0; j < numCourses; j++) {
                if(adj[i][j] == 1) {
                    adj[i][j] = 0;
                    indegree[j]--;
                    
                    // 重复以上步骤直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止
                    if(indegree[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }
        
        return count == numCourses ? result : (new int[0]);
    }
}

最小生成树

给定一个无方向的带权图 G=(V, E)，最小生成树为集合 T，T 是以最小代价连接 V 中所有顶点所用边E的最小集合。集合 T 中的边能够形成一颗树，这是因为每个节点（除了根节点）都能向上找到它的一个父节点。它包含全部 n 个顶点及 n - 1 条边。

Kruskal 算法

此算法可以称为 “加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

把图中的所有边按代价从小到大排序；
把图中的 n 个顶点看成独立的 n 棵树组成的森林；
按权值从小到大选择边，所选的边连接的两个顶点 ui，vi 应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
重复上述步骤，直到所有顶点都在一颗树内或者有 n-1 条边为止。

如图所示：

Kruskal 算法

Prime 算法

此算法可以称为 “加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点 s 开始，逐渐长大覆盖整个连通网的所有顶点。

图的所有顶点集合为 V；初始令集合 u = {s}，v = V−u;
在两个集合u，v能够组成的边中，选择一条代价最小的边 (u0, v0)，加入到最小生成树中，并把 v0 并入到集合 u 中。
重复上述步骤，直到所有顶点都在一颗树内或者有 n-1 条边为止。

如图所示：

Prime 算法

引用：
数据结构与算法：图和图算法(一)
Representing graphs
图的基本算法（最小生成树）
算法导论--最小生成树（Kruskal和Prim算法）

数据结构 图的表示及相关算法&LeetCode题目

图的基本概念

顶点的度

路径、路径长度和回路

图的存储结构（表示图）

边的集合 Edge lists

邻接矩阵 Adjacency matrices

邻接表 Adjacency lists

图的两种遍历方法

深度优先搜索遍历 DFS

广度优先搜索遍历 BFS

查找最短路径

拓扑排序

最小生成树

Kruskal 算法

Prime 算法

数据结构图的表示及相关算法&LeetCode题目