【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树(上)

简介: 【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

🔥前言

本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面试真题,面试、找工作完全可以来这里找机会。此外,网站内的编码主题多样化,调试功能可运用性强,可谓是非常注重用户体验。这么好的免费刷题网站还不快入手吗,快去注册开启算法百炼成神之路吧!


1、AB13 【模板】拓扑排序

学会使用邻接表解决图论问题,巧妙利用vector容器


题目链接:拓朴排序


85f811d96cd44822a84ada34d41a3710.png


1.1、解题思路

解决拓扑排序之前要先认识什么是拓扑排序:


对一个有向无环图(Directed Acyclic Graph简称DAG)图G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。


解决步骤:


使用邻接表将顶点联系起来,辅助数组inDegree表示每个顶点的入度。

借助队列和计数器变量来判断该有向图是否有环:

将入度为零的顶点入队(也就是拓扑图第一个顶点)

取队首,遍历与之相邻的顶点,若该顶点入度减一后为零就将其入队

只要队列非空就循环操作,计算器循环加一,与顶点数比较是否相等

本题末尾也不能输出空格,因此输出拓扑序列时要加限制条件

1.2、代码实现与注释

本题源码:

#include<iostream>
#include<vector>
#include<queue>
#define M 200001
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> adjList[M]; // 模拟邻接表
    int inDegree[M] = { 0 };// 记录每个顶点的入度
    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        adjList[a].push_back(b);
        inDegree[b]++;
    }
    queue<int> que; // 将初始入度为零的顶点入队
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0)
            que.push(i);
    }
    int cnt = 0; // 用来计数,判断改图是否有环
    vector<int> res; // 用来输出顶点序列
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        res.push_back(u);
        for (int i = 0; i < adjList[u].size(); i++) { // 遍历u的相邻顶点
            int v = adjList[u][i];
            if (--inDegree[v] == 0)
                que.push(v);
        }
        cnt++;
    }
    // 若计数器与顶点数相同则图无环,存在拓扑排序
    if (cnt == n) {
        for (int i = 0; i < res.size(); i++) {
            cout << res[i];
            // 限制输出空格的条件
            if (i != res.size() - 1) {
                cout << " ";
            }
        }
    } else {
        cout << -1;
    }
    return 0;
}

重要注释:


adjList数组是vector类型的,用来模拟邻接表

使用每个元素为一个数组的vector容器模拟邻接表进行建图

vector[a]所对应的数组中存储着该顶点所指向的其他顶点

inDegree数组代表每一个顶点的入度情况

使用一个队列,初始时将所有入度为0的顶点全部入队,之后采用BFS的思想:

依次取出队头元素并存入结果数组中,然后在邻接表中遍历该队头元素所指向的其他顶点

将这些顶点的入度全部减一,若减一后某顶点的入度变为0,则将该顶点进行入队操作,

重复此步骤直至队列为空为止。

设置一个用于判断图中是否存在环(是否可以得到拓扑序列)的计数器,在弹出队头元素后要将计数器加一,最后队列为空后,若计数器的值与顶点数相同,则说明图不存在环,可以得到拓扑序列。


目录
相关文章
|
5月前
|
机器学习/深度学习 人工智能 算法
深度学习入门:理解神经网络与反向传播算法
【9月更文挑战第20天】本文将深入浅出地介绍深度学习中的基石—神经网络,以及背后的魔法—反向传播算法。我们将通过直观的例子和简单的数学公式,带你领略这一技术的魅力。无论你是编程新手,还是有一定基础的开发者,这篇文章都将为你打开深度学习的大门,让你对神经网络的工作原理有一个清晰的认识。
|
23天前
|
存储 传感器 算法
使用贪心算法解决最小生成树问题
大家好,我是V哥。今天聊聊贪心算法解决最小生成树问题。面试中遇到此类题目,需掌握Prim和Kruskal算法。Prim适合稠密图,Kruskal适合稀疏图。两者时间复杂度分别为O(m log n)和O(m log m),各有优缺点。应用场景广泛,包括图像处理、传感器网络、社交网络分析等。关注V哥,全栈之路一起走。
|
3月前
|
机器学习/深度学习 算法 Python
机器学习入门:理解并实现K-近邻算法
机器学习入门:理解并实现K-近邻算法
54 0
|
4月前
|
机器学习/深度学习 算法
机器学习入门(三):K近邻算法原理 | KNN算法原理
机器学习入门(三):K近邻算法原理 | KNN算法原理
|
4月前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
4月前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)
|
4月前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
|
4月前
|
算法 决策智能
基于prim算法求出网络最小生成树实现网络社团划分和规划
该程序使用MATLAB 2022a版实现路线规划,通过排序节点权值并运用Prim算法生成最小生成树完成网络规划。程序基于TSP问题,采用遗传算法与粒子群优化算法进行路径优化。遗传算法通过编码、选择、交叉及变异操作迭代寻优;粒子群优化算法则通过模拟鸟群觅食行为,更新粒子速度和位置以寻找最优解。
|
27天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
27天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
135 68