算法.图论-建图/拓扑排序及其拓展

建图的三种方式

我们建图的三种方式分别是邻接矩阵, 邻接矩阵, 链式前向星

邻接矩阵

假设我们的点的个数为N个, 我们就把他们的下标依次标为1, 2 ,…, 然后在一个矩阵表上进行边的添加, 比如我要在点2和点4之间添加一个权值为5的边, 那么我就在矩阵matrix[2][4] = 5即可, 唯一注意的就是如果是无向图, 就需要把matrix[4][2]位置也设置为5, 所以这个方法的弊端是十分明显的, 就是消耗的空间过大, 所以我们在大厂的笔试或者是比赛, 不会用这种方式进行建图, 下面是邻接矩阵法的代码实现

public class day23 {
    public static void main(String[] args) {
        int[][] edges = {{1,2,5},{5,3,1},{1,4,4},{2,5,2}};
        //测试一下使用邻接矩阵法建图
        GraphUseMatrix graphUseMatrix = new GraphUseMatrix();
        graphUseMatrix.build(5);
        graphUseMatrix.directGraph(edges);
        //graphUseMatrix.unDirectGraph(edges);
        graphUseMatrix.showGraph();
    }
}

/**
 * 邻接矩阵建图的方法
 * 下面我们介绍的所用的图都是带权值的图, 不带权的更简单就不说了
 */
class GraphUseMatrix{
    //设置一个最大的点数(根据题意)
    private static final int MAXN = 11;
    //设置一个最大的边数(根据题意, 无向图 * 2)
    private static final int MAXM = 21;

    //构建一个当前的点数curn
    private static int curN = 0;
    //设置一个邻接的矩阵(大小就是(点数 + 1) * (点数 + 1), 这里我们保证是够用的)
    private static final int[][] matrix = new int[MAXN][MAXN];

    //初始化矩阵的方法(传入的点的数量)
    public void build(int n){
        curN = n;
        //清空矩阵的脏数据
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                //把邻接矩阵中的数据刷为最大值(因为权值可能为0)
                matrix[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    //添加边的方法
    private void addEdge(int from, int to, int weight){
        matrix[from][to] = weight;
    }

    //在有向带权图中添加边
    public void directGraph(int[][] edges){
        for(int[] edge : edges){
            addEdge(edge[0], edge[1], edge[2]);
        }
    }

    //在无向带权图中添加边
    public void unDirectGraph(int[][] edges){
        for(int[] edge : edges){
            addEdge(edge[0], edge[1], edge[2]);
            addEdge(edge[1], edge[0], edge[2]);
        }
    }

    //展示图的方式
    public void showGraph(){
        System.out.println("邻接矩阵法建图展示");
        for(int i = 1; i <= curN; i++){
            for(int j = 1; j <= curN; j++){
                if(matrix[i][j] == Integer.MAX_VALUE){
                    System.out.print("∞  ");
                }else{
                    System.out.print(matrix[i][j] + "  ");
                }
            }
            System.out.println();
        }
    }
}

上述代码的测试结果见下

测试结果也是很明显的, 证明我们之前的代码是没有问题的, 无向图总体是按照正对角线呈对称分布

邻接表

邻接表是一种动态的建图的方式, 关于大厂的笔试面试题, 邻接表以及完全够用了, 如果涉及到比赛内容的话, 我们会使用链式前向星建图法, 等会我们会介绍到这种算法, 说回来邻接表, 其实就是一个
ArrayList<ArrayList<int(无权)/int>的结构, 也就是顺序表套顺序表的结构, 假如我们要建立一个从点2到点4的边,如果不带权值, 我们就让外层顺序表2下标对应的顺序表添加一个元素4, 如果同时带有一个权值的话, 我们就添加一个数组(假设权值是8)我们就让2下标对应的顺序表添加一个[4,8]数组, 下面是邻接表的代码实现

public class day23 {
    public static void main(String[] args) {
        int[][] edges = {{1, 2, 5}, {5, 3, 1}, {1, 4, 4}, {2, 5, 2}};
//        //测试一下使用邻接矩阵法建图
//        GraphUseMatrix graphUseMatrix = new GraphUseMatrix();
//        graphUseMatrix.build(5);
//        graphUseMatrix.unDirectGraph(edges);
//        graphUseMatrix.showGraph();

        //测试一下邻接表法建图
        GraphUseList graphUseList = new GraphUseList();
        graphUseList.build(5);
        graphUseList.directGraph(edges);
        //graphUseList.unDirectGraph(edges);
        graphUseList.showGraph();
    }
}

/**
 * 邻接表建图的方法(是一种动态的结构)
 * 和邻接矩阵一样, 我们在这里介绍的都是带权的图
 */
class GraphUseList {

    //构建一个当前的点数
    private static int curN = 0;

    //邻接表的主体
    private static ArrayList<ArrayList<int[]>> list = new ArrayList<>();

    //初始化邻接表(传入一个点的数量)
    public void build(int n) {
        //设置当前的点数
        curN = n;
        //上来直接清空邻接表
        list.clear();
        //开始构建顺序表(新添加n+1个列表)
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
    }

    //添加边的方法
    private void addEdge(int from, int to, int weight) {
        list.get(from).add(new int[]{to, weight});
    }

    //构建一个有向的图
    public void directGraph(int[][] edges) {
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
        }
    }

    //构建一个无向的图
    public void unDirectGraph(int[][] edges) {
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
            addEdge(edge[1], edge[0], edge[2]);
        }
    }

    //展示邻接表图的方式
    public void showGraph() {
        System.out.println("邻接表法建图展示");
        for (int i = 1; i <= curN; i++) {
            System.out.print("点" + i + "(邻点/权值) : ");
            for (int[] elem : list.get(i)) {
                System.out.print("[" + elem[0] + "," + elem[1] + "]");
            }
            System.out.println();
        }
    }
}

执行结果如下图所示

链式前向星

前两种建图的方式都有着明显的缺点, 第一个虽然是静态空间但是空间的大小过大, 第二个虽然使用的空间不是很大但是是一种动态的结果, 就会在时间上大打折扣, 所以我们就想要一种既可以是静态空间又可以做到省空间省时间的结构, 我们就需要下面的链式前向星建图法, 这个方法有点类似与前缀树的静态空间建树法(之前有)和链表头插法的结合, 下面我们分析一下建图的过程

准备过程 :
我们准备三个数组, 把每一个加入的边都设置一个编号(从1开始逐渐增加)

具体的例子
假设此时我们准备了五个点, 然后执行4次加边的操作
head数组长度准备为 6 (5 + 1) , next, to, weight 数组的长度都准备 5 (4 + 1)
下面执行加边的过程

[3,1,2], 这条边编号为1, 出发点是3, 终点是1, 权值是2, 在head中插入头边head[3] = 1(这里就是用的头插法, 这里是首条边), next[1] = 0 (头边所以是0) , to[1] = 1, weight[1] = 2

代码实现如下

public class day23 {
    public static void main(String[] args) {
        int[][] edges = {{1, 2, 5}, {5, 3, 1}, {1, 4, 4}, {2, 5, 2}};
//        //测试一下使用邻接矩阵法建图
//        GraphUseMatrix graphUseMatrix = new GraphUseMatrix();
//        graphUseMatrix.build(5);
//        graphUseMatrix.unDirectGraph(edges);
//        graphUseMatrix.showGraph();

//        //测试一下邻接表法建图
//        GraphUseList graphUseList = new GraphUseList();
//        graphUseList.build(5);
//        graphUseList.unDirectGraph(edges);
//        graphUseList.showGraph();

        //测试一下链式前向星建图
        GraphUseLinkedStar graphUseLinkedStar = new GraphUseLinkedStar();
        graphUseLinkedStar.build(5);
        graphUseLinkedStar.unDirectGraph(edges);
        graphUseLinkedStar.showGraph();
    }
}


/**
 * 链式前向星建图法(静态的建图法)
 */
class GraphUseLinkedStar {
    //定义点最大值
    private static final int MAXN = 11;
    //定义边最大值
    private static final int MAXM = 22;
    //构建head数组(以点为准)
    private static final int[] head = new int[MAXN];
    //构建next数组(以边为准)
    private static final int[] next = new int[MAXM];
    //准备to数组(以边为主)
    private static final int[] to = new int[MAXM];
    //准备weight数组(以边为主)
    private static final int[] weights = new int[MAXM];
    //定义一下当前点的个数
    private static int curN = 0;
    //定义一个计数器用于给边编号
    private static int cnt = 0;

    //传入一个点数n用来初始化图结构
    public void build(int n){
        //更新计数器
        cnt = 1;
        //初始化当前节点个数
        curN = n;
        //清除head即可(这里不用重置to, weights, next)
        Arrays.fill(head, 1, n + 1, 0);
    }

    //添加边的方法(其实就是链表的头插法)
    private void addEdge(int from, int ton, int weight){
        next[cnt] = head[from];
        to[cnt] = ton;
        weights[cnt] = weight;
        head[from] = cnt++;
    }

    //构建一个有向带权图
    public void directGraph(int[][] edges){
        for(int[] edge : edges){
            addEdge(edge[0], edge[1], edge[2]);
        }
    }

    //构建一个无向带权图
    public void unDirectGraph(int[][] edges){
        for(int[] edge : edges){
            addEdge(edge[0],edge[1],edge[2]);
            addEdge(edge[1],edge[0],edge[2]);
        }
    }

    //展示图的方法(类似于链表的遍历)
    public void showGraph(){
        System.out.println("链式前向星建图展示");
        for(int i = 1; i <= curN; i++){
            System.out.print("点" + i + "(邻点/权值) : ");
            for(int ei = head[i]; ei != 0; ei = next[ei]){
                System.out.print("[" + to[ei] + "," + weights[ei] + "]");
            }
            System.out.println();
        }
    }
}

执行结果如下

拓扑排序

拓扑排序基础原理介绍

拓扑排序的存在条件是在一个有向且无环图中的排序, 拓扑排序在某种程度上反应的是一件事的执行的先后顺序, 请看下图

这张图中, 黑色的字符表示节点的名称, 蓝色的数字指的是该位置的入度是多少, 上面我们提到过, 拓扑排序的过程可以视为完成某一件事的先后顺序, 假设我们最终想要完成的任务是f, 那我们下面的字符的序列也就是完成最终事件的顺序
拓扑排序不是唯一的, 比如下面的图

在这张图中, 先完成a还是先完成b都是可以的, 所以产生的拓扑排序的情况就有两种, 这就说明拓扑排序的结果可能有多种, 只要满足每一个节点的前面所需要的节点都完成了就可以
拓扑排序的应用举例 :
比如在计算机编译程序的过程中, 编译一个程序需要另外的程序结果才能编译完成, 所以很自然的就会出现程序编译的先后顺序问题, 见下图, 左侧的表格是编译一个程序所需要的已经完成的编译结果, 右面是完成a的编译过程的图, 右下角的两串字符串都是完成的顺序, 这同样说明拓扑排序不是唯一的

拓扑排序要求一个图有向, 这个很好理解, 做事情的步骤肯定是有先后的顺序的, 而且要无环, 这个我们就拿上面的编译过程理解, 假如a的编译过程依赖b, b的编译过程依赖a, 那这不就是矛盾了吗, 两者互相依赖谁也完成不了

拓扑排序步骤解析

实现拓扑排序用的是零入度删除法, 需要用到队列(特殊状况下用小根堆), 核心就是删除0入度的节点和因为该节点所造成的入度影响
这就解释了上面的图为什么我们要进行入度的标记, 首先图解一下0入度删除法的步骤

最终组合出来的删除节点的步骤就是最终的拓扑排序的答案

拓扑排序模板leetcode-课程表

leetcode210-课程表题目链接

class Solution {
    //我们采用邻接表建图就已经够用了
    private static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    //课的最大数目
    private static final int MAXN = 2001;
    //同时定义一个入读表
    private static final int[] indegree = new int[MAXN];
    //当前的数据个数
    private static int curN = 0;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        build(numCourses);
        directGraph(prerequisites);
        //定义一个计数器看一看队列弹出了多少次(建议使用数组形式队列)
        int cntNum = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        //首先遍历入度数组加入入度为0的节点
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        //从队列中逐渐弹出元素进行判断
        int[] res = new int[numCourses];
        while (!queue.isEmpty()) {
            int index = queue.poll();
            //在返回数组中添加上该元素
            res[cntNum++] = index;
            //遍历其所属的列表删除这个元素造成的入度
            for(int elem : list.get(index)){
                if(--indegree[elem] == 0){
                    queue.offer(elem);
                }
            }
        }
        return cntNum == res.length ? res : new int[0];
    }

    //初始化图结构
    private static void build(int n) {
        //更新当前的数据个数
        curN = n;
        //更新顺序表
        list.clear();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        //更新入度表
        Arrays.fill(indegree, 0, n, 0);
    }

    //建图的主函数(本质是有向无权图), 建图的过程中同时完成入度的统计
    private static void directGraph(int[][] edges) {
        for (int[] edge : edges) {
            addEdge(edge[1], edge[0]);
            indegree[edge[0]]++;
        }
    }

    //插入边的函数
    private static void addEdge(int from, int to) {
        list.get(from).add(to);
    }
}

拓扑排序拓展

关于拓扑排序的最基础的用法我们在上一节就已经探讨过了, 这节课我们讨论的是拓扑排序的最重要的技巧, 就是根据拓扑排序逐段的向下推送消息, 其实有点类似于树形dp

食物链计数

上面我们仅仅介绍了一部分流程而已, 但是整体上的逻辑就是这样的, 建图之后跑拓扑排序, 然后计数即可
洛谷-食物链测试链接
代码实现如下, 使用的是链式前向星的建图方式, 然后注意一下比赛平台的IO方式即可

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.IOException;
//计算食物链的条数, 用的是一种向下推送的技巧(建图使用链式前向星建图法)
public class Main{

    private static final int MAXN = 5001;

    private static final int MAXM = 500001;

    private static final int[] head = new int[MAXN];

    private static final int[] next = new int[MAXM];

    private static final int[] to = new int[MAXM];

    private static final int[] indegree = new int[MAXN];

    private static final int[] ans = new int[MAXN];

    private static int resCnt = 0;

    private static int cnt = 0;

    private static final int MOD = 80112002;

    //拓扑排序时需要的队列我们就使用动态的结构模拟看看过不过
    private static final Queue<Integer> queue = new ArrayDeque<>();

    //初始化图的函数
    private static void build(int n){
        cnt = 1;
        resCnt = 0;
        Arrays.fill(head, 0, n + 1, 0);
        Arrays.fill(indegree, 0, n + 1, 0);
        Arrays.fill(ans, 0, n + 1, 0);
        queue.clear();
    }

    //添加边的函数(链式前向星的加边方式, 同时修改入度)
    private static void addEdge(int fro, int t){
        next[cnt] = head[fro];
        to[cnt] = t;
        head[fro] = cnt++;
        indegree[t]++;
    }

    //拓扑排序的过程
    private static void topoSort(int n){
        //首先添加0入度的点入队列(同时在ans中修改等待推送)
        for(int i = 1; i <= n; i++){
            if(indegree[i] == 0){
                queue.offer(i);
                ans[i] = 1;
            }
        }

        //开始进行排序的主逻辑
        while(!queue.isEmpty()){
            int po = queue.poll();
            if(head[po] == 0){
                //此时说明该点是末尾的节点, 直接计数
                resCnt = (ans[po] + resCnt) % MOD;
            }else{
                //此时继续链式前向星的遍历过程
                for(int ei = head[po]; ei > 0; ei = next[ei]){
                    ans[to[ei]] = (ans[to[ei]] + ans[po]) % MOD;
                    if(--indegree[to[ei]] == 0){
                        queue.offer(to[ei]);
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        //下面的while循环其实就是建图的过程
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            int n = (int)in.nval;
            build(n);
            in.nextToken();
            int opSize = (int)in.nval;
            for(int i = 0; i < opSize; i++){
                in.nextToken();
                int fro = (int)in.nval;
                in.nextToken();
                int t = (int)in.nval;
                addEdge(fro, t);
            }
            //下面就去跑拓扑排序
            topoSort(n);
            out.println(resCnt);
        }
        
        out.flush();
        out.close();
        br.close();
    }
}

喧闹与富有

leetcode851.喧闹与富有题目链接
总体上说这个题没什么分析的难度, 就是简单的建出来图之后然后跑拓扑排序就可以了, 传递的信息就是最安静的人的下标, 注意初始化ans数组的时候就把ans数组中每个位置的值初始化为本身的下标(因为自己的安静值肯定是一个限制值)
代码实现如下

//使用链式前向星的建图方式
class LoudAndRich {
    
    private static final int MAXN = 501;

    private static final int MAXM = MAXN * (MAXN - 1) / 2;

    private static final int[] head = new int[MAXN];

    private static final int[] next = new int[MAXM];

    private static final int[] to = new int[MAXM];

    private static final int[] indegree = new int[MAXN];

    private static int cnt = 0;

    private static int curN = 0;

    private static final Queue<Integer> queue = new ArrayDeque<>();

    //初始化图的函数
    private static void build(int n){
        cnt = 1;
        curN = n;
        Arrays.fill(head, 0, n + 1, 0);
        Arrays.fill(indegree, 0, n + 1, 0);
        queue.clear();
    }

    //添加边的函数(同时统计入度)
    private static void addEdge(int fro, int t){
        next[cnt] = head[fro];
        to[cnt] = t;
        head[fro] = cnt++;
        indegree[t]++;
    }

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        //建图
        int len = quiet.length;
        build(len);
        for(int[] edge : richer){
            addEdge(edge[0], edge[1]);
        }

        //初始化一个答案数组
        int[] ans = new int[len];
        for(int i = 0; i < len; i++){
            ans[i] = i;
        }
        //跑拓扑排序
        topoSort(ans, quiet);
        return ans;
    }

    private static void topoSort(int[] ans, int[] quiet){
        //首先找到0入度的点加入队列
        for(int i = 0; i < curN; i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }

        //遍历图进行ans数组的修改
        while(!queue.isEmpty()){
            int curPointer = queue.poll();
            for(int ei = head[curPointer]; ei > 0; ei = next[ei]){
                if(--indegree[to[ei]] == 0){
                    queue.offer(to[ei]);
                }
                ans[to[ei]] = quiet[ans[curPointer]] < quiet[ans[to[ei]]] ? ans[curPointer] : ans[to[ei]];
            }
        }
    }
}

并行课程

其实就是一个简单的拓扑排序, 建图的时候我们使用了一个新的辅助空间
代码实现如下

class Cource {

    private static final int MAXN = 50001;

    private static final int MAXM = 50001;

    private static final int[] head = new int[MAXN];

    private static final int[] next = new int[MAXM];

    private static final int[] to = new int[MAXM];

    private static final int[] indegree = new int[MAXN];

    private static int curN = 0;

    private static int cnt = 0;

    private static int res = Integer.MIN_VALUE;

    private static final Queue<Integer> queue = new ArrayDeque<>();

    //专属于本题的辅助数组(用于结算新加的time)
    private static final int[] need = new int[MAXN];

    private static final int[] ans = new int[MAXN];

    //初始化图的函数
    private static void build(int n, int[] time){
        cnt = 1;
        curN = n;
        res = Integer.MIN_VALUE;
        Arrays.fill(head, 0, n + 1, 0);
        Arrays.fill(need, 0, n + 1, 0);
        Arrays.fill(indegree, 0, n + 1, 0);
        queue.clear();
        //初始化ans数组
        for(int i = 1; i <= time.length; i++){
            res = Math.max(res, time[i - 1]);
            ans[i] = time[i - 1];
        }
    }

    //添加边的函数(顺带统计入度)
    private static void addEdge(int fro, int t){
        next[cnt] = head[fro];
        to[cnt] = t;
        head[fro] = cnt++;
        indegree[t]++;
    }

    public int minimumTime(int n, int[][] relations, int[] time) {
        //初始化并建图
        build(n, time);
        for(int[] edge : relations){
            addEdge(edge[0], edge[1]);
        }

        //下面就是拓扑排序的主流程
        topoSort();
        return res;
    }

    private static void topoSort(){
        //首先添加入度为0的点入队列
        for(int i = 1; i <= curN; i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }

        //开始进行拓扑排序的主流程
        while(!queue.isEmpty()){
            int courceNum = queue.poll();
            if(indegree[courceNum] == 0){
                //说明这个时候可以结算了
                ans[courceNum] += need[courceNum];
                res = Math.max(res, ans[courceNum]);
            }else{
                for(int ei = head[courceNum]; ei > 0; ei = next[ei]){
                    need[to[ei]] = Math.max(need[to[ei]], ans[courceNum]);
                    if(--indegree[to[ei]] == 0){
                        queue.offer(to[ei]);
                    }
                }
            }
        }
    }
}