程序员经验分享-hwhale

拓扑排序详解

2023-05-16

提示：古人学问无遗力 少壮功夫老始成，纸上得来终觉浅 觉知此事须躬行

文章目录

  • 一、AOV网的特点
  • 二、问题
  • 三、拓扑排序
  • 四、拓扑排序的方法
  • 五、检查AOV网中是否存在一个环
  • 六、两种思路
    • 6.1、思路一
      • 6.1.1、思路一代码实现
      • 6.1.2、思路一运行截图
    • 6.2、思路二
      • 6.2.1、思路二代码
      • 6.2.2、运行结果
  • 七、可执行代码汇总
  • 总结

一、AOV网的特点

1、若是从i到j有有一条有向路径，则i是j的前驱，j是i的后继
2、若<i,j> 是网中有向边，则i是j的直接前驱，j是i的直接后继
3、AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然不可能

二、问题

我们要解决如下两个问题
1、如何进行拓扑排序
2、如何判别AOV网中是否存在回路

三、拓扑排序

在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得AOV网中有弧<i,j>存在 则在这个序列中，i 一定排在j的前面 具有这种线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序

四、拓扑排序的方法

1、在有向图中选一个没有前驱的顶点且输出
2、从图中删除该顶点和所有以他为尾的弧
3、重复上述步骤，直到所有的顶点均已输出，或者当图中不存在无前驱的顶点为止
请添加图片描述

比如我们要对上述图进行拓扑排序 第一次寻找的是A这一个结点 因为A没有前驱 接下来就是删除A以及以A为弧尾的弧，此时就是如下图
请添加图片描述
在从中选择一个没有前驱的结点，这里BCD 都可以，这里我们就选择B 同样的道理 删除B以及以B为弧尾的弧此时就是如下图
请添加图片描述
同样的道理 再选一个C删除以C为弧尾的弧
请添加图片描述
再删除 D
请添加图片描述

再删除E
所有总的拓扑排序是 当然排序可能不止一种 因为可能不止一个结点在某一步骤中是无前驱的
ABCDE 有人可能会说了这个图太简单了，能不能难一点的图来拓扑
如下
请添加图片描述
拓扑排序可以如下
AEBDC
EABDC
AEDBC
EADBC

五、检查AOV网中是否存在一个环

对有向图构造其顶点的拓扑有序序列，若是网中所有顶点都在它的拓扑有序序列中，则该AOV 网必定不存在环 若是最后还剩下几个顶点必然是存在环，如下图
请添加图片描述

第一次我们删除的是A 第二次我们就找不到没有前驱的节点了 所以就可以判断是存在回路的

六、两种思路

6.1、思路一

1、需要知道那些结点没有前驱 也就是入度为零 怎么找到呢？
本来想着可以使用逆邻接表来实现 不过也确实可以 但是这里依然使用邻接矩阵的方式
我们知道存储有向图的时候 邻接矩阵中行表示的是每一个结点的出度，那么列其实自然就是每一个结点的入度了 这样我们使用一个for就可以知道哪一个结点的入度为零了 但是这样其实你也可以感觉到没有逆邻接表高效， 所以使用另外一种方式就是使用一个count数组来记录每一个结点当前的入度 这样在遍历的过程中一直修改count[]数组 并查看count数组中为零的可以输出 并将其中的值设置为一个标记 比如说-1 表示结点已经被删除 当count数组中的所有的count都为-1时也就可以跳出循环
2、如何删除顶点对应的出度
通过查看邻接矩阵，可以知道与待删除结点关联的结点，此时将对应的结点的count[]中的值减一即可

6.1.1、思路一代码实现

这里我使用了许多的日志 方便进行代码的调试 当时同样的很影响运行的时间

void TopologicalSort(AMGraph &G){
	int count[G.vexnum]={0};
	//初始状每一个结点的入度 也就是计算出count数组
	//通过计算邻接矩阵中每一列 来统计入度 
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[j][i])count[i]++;
		} 
	} 
	//从中选择一个入度为零的 
	int i=0; vector<char> V;
	for(int x=0;x<G.vexnum;x++){//表示要循环的次数 
	 	int i=0; 
		while(count[i++]!=0);
		if(i>G.vexnum){//说明没有找到的 此时就要退出了  但是还需要判断是因为环才退出的 还是遍历完成 
			cout<<"存在环"<<endl; 
			return;
		} 
		else{//找到待删除的点  将其count置为-1 并将其关联的count数目减一 
			count[i-1]=-1;//-1是作为一种标记
			cout<<"将"<<G.vexs[i-1]<<"加入到容器中"<<endl; 
			V.push_back(G.vexs[i-1]); 
			for(int j=0;j<G.vexnum;j++){
				if(G.arcs[i-1][j]){//若是存在边，则将边删除 并处理count数组 
					//G.arcs[i-1][j]=0;
					count[j]-=1; 
				}
			} 
		} 
		cout<<"此时的count数组是"<<endl; 
		for(int H=0;H<G.vexnum;H++){
			cout<<count[H]<<" "; 
		}
		cout<<endl;
	}
		for(int i=0;i<G.vexnum;i++){
			cout<<V[i]<<" ";
		}
		cout<<endl;
}

6.1.2、思路一运行截图

使用用图就是上述的两个图
输入方式
请添加图片描述
第一个图的运行结果
请添加图片描述
第二个有环图的运行结果
请添加图片描述

6.2、思路二

使用栈（或者队列）的结构：首先计算所有顶点的初始入度，然后将count初值为零的顶点全部入栈，再将栈中的顶点依次出栈（出栈的同时修改其所有邻接顶点的入度，若为零则邻接顶点也入栈）。由于有n个顶点，因此出栈的操作应该循环n次；若在少于n次时栈已经空了，说明图中存在回路。这种方式较上种优化的地方是 不需要每一次都查找哪一个count==0 了

6.2.1、思路二代码

void TopologicalSort(AMGraph &G){
	int count[G.vexnum]={0};
	vector<char> result;//用来存放结果 
	stack<int> S;//定义一个栈 其中存放count值为零的角标 
	//初始状每一个结点的入度 也就是计算出count数组
	//通过计算邻接矩阵中每一列 来统计入度 
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[j][i])count[i]++;
		} 
	} 
	//将可以此时count==0的结点 也就是可以遍历的放入栈中 
	for(int i=0;i<G.vexnum;i++){
		if(0==count[i]){
			cout<<"将"<<G.vexs[i]<<"放入栈中"<<endl; 
			S.push(i);
		}
	} 
	for(int h=0;h<G.vexnum;h++){//n个结点需要执行n次 
		if(S.empty()){
			//要么有环 要么处理完毕 
			break; 
		} 
		int cur=S.top();
		S.pop();
		cout<<"将"<<G.vexs[cur]<<"放入结果集中"<<endl; 
		result.push_back(G.vexs[cur]);
		//同时需要将count处理的，下面处理count数组
		count[cur]=-1; 
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[cur][j]){
				count[j]-=1;
				G.arcs[cur][j]=0;
			}
			if(count[j]==0){
				cout<<"将"<<G.vexs[j]<<"放入栈集中"<<endl;
				S.push(j);
			}
		} 	
	}
	if(result.size()==G.vexnum){
		for(int i=0;i<G.vexnum;i++){
			cout<<result[i]<<" ";
		}
		cout<<endl;
	}
	else cout<<"此时存在环"<<endl;
}

6.2.2、运行结果

用的测试图是上文中的三个测试图
第一个的输入方式
请添加图片描述

第二个的输入的方式与第一个一样 这里太长 就直接放结果吧
请添加图片描述

第三个测试图
请添加图片描述

七、可执行代码汇总 

#include<bits/stdc++.h>
using namespace std;
#define MaxInt 32767  //表示极大值∞  其实就是一种无穷标志
#define MVNum  100    //表示最大顶点数 
typedef char VerTexType;//假设顶点的数据结构类型为char 
typedef int  ArcType;//假设权值类型为整形
//下面的是邻接矩阵的 
typedef struct{
	 VerTexType vexs[MVNum];//顶点表 
	 ArcType  arcs[MVNum][MVNum];//邻接矩阵 
	 int vexnum;//图的当前顶点数
	 int arcnum;//图的当前边数
}AMGraph;
//创建一个无向图 ，其实就是填充两个数组 
void CreateAdjoin(AMGraph &G){
	cout<<"请输入顶点数和边数"<<endl;
	cin>>G.vexnum>>G.arcnum; 
	cout<<"请输入各个顶点名称"<<endl; 
	for(int i=0;i<G.vexnum;i++){
		cin>>G.vexs[i]; 
	}
	for(int h=0;h<G.arcnum;h++){
		char vex1;char vex2;
		cout<<"请输入弧的两个顶点(类如从A指向B则输入AB)"<<endl;
		cin>>vex1>>vex2;
		//首先来看是否存在这两个顶点  若是存在则找到这两个点对应的下标
		// 当然创建的时候一种更加简单的方式就是遍历二维数组 一个一个输入
		int i=0;while(G.vexs[i++]!=vex1);
		int j=0;while(G.vexs[j++]!=vex2);
		if(i>G.vexnum||j>G.vexnum){//没有找到 
			cout<<"你输入的结点值不正确"<<endl; 
		}
		else{
			cout<<"请输入此边对应的权重"<<endl; 
			cin>>G.arcs[i-1][j-1];
			//G.arcs[j-1][i-1]=G.arcs[i-1][j-1];
		}
	}
} 
void TopologicalSort1(AMGraph &G){
	int count[G.vexnum]={0};
	//初始状每一个结点的入度 也就是计算出count数组
	//通过计算邻接矩阵中每一列 来统计入度 
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[j][i])count[i]++;
		} 
	} 
	//从中选择一个入度为零的 
	int i=0; vector<char> V;
	for(int x=0;x<G.vexnum;x++){//表示要循环的次数 
	 	int i=0; 
		while(count[i++]!=0);
		if(i>G.vexnum){//说明没有找到的 此时就要退出了  但是还需要判断是因为环才退出的 还是遍历完成 
			cout<<"存在环"<<endl; 
			return;
		} 
		else{//找到待删除的点  将其count置为-1 并将其关联的count数目减一 
			count[i-1]=-1;//-1是作为一种标记
			cout<<"将"<<G.vexs[i-1]<<"加入到容器中"<<endl; 
			V.push_back(G.vexs[i-1]); 
			for(int j=0;j<G.vexnum;j++){
				if(G.arcs[i-1][j]){//若是存在边，则将边删除 并处理count数组 
					//G.arcs[i-1][j]=0;
					count[j]-=1; 
				}
			} 
		} 
		cout<<"此时的count数组是"<<endl; 
		for(int H=0;H<G.vexnum;H++){
			cout<<count[H]<<" "; 
		}
		cout<<endl;
	}
		for(int i=0;i<G.vexnum;i++){
			cout<<V[i]<<" ";
		}
		cout<<endl;
}
void TopologicalSort2(AMGraph &G){
	int count[G.vexnum]={0};
	vector<char> result;//用来存放结果 
	stack<int> S;//定义一个栈 其中存放count值为零的角标 
	//初始状每一个结点的入度 也就是计算出count数组
	//通过计算邻接矩阵中每一列 来统计入度 
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[j][i])count[i]++;
		} 
	} 
	//将可以此时count==0的结点 也就是可以遍历的放入栈中 
	for(int i=0;i<G.vexnum;i++){
		if(0==count[i]){
			cout<<"将"<<G.vexs[i]<<"放入栈中"<<endl; 
			S.push(i);
		}
	} 
	for(int h=0;h<G.vexnum;h++){//n个结点需要执行n次 
		if(S.empty()){
			//要么有环 要么处理完毕 
			break; 
		} 
		int cur=S.top();
		S.pop();
		cout<<"将"<<G.vexs[cur]<<"放入结果集中"<<endl; 
		result.push_back(G.vexs[cur]);
		//同时需要将count处理的，下面处理count数组
		count[cur]=-1; 
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[cur][j]){
				count[j]-=1;
				G.arcs[cur][j]=0;
			}
			if(count[j]==0){
				cout<<"将"<<G.vexs[j]<<"放入栈集中"<<endl;
				S.push(j);
			}
		} 	
	}
	if(result.size()==G.vexnum){
		for(int i=0;i<G.vexnum;i++){
			cout<<result[i]<<" ";
		}
		cout<<endl;
	}
	else cout<<"此时存在环"<<endl;
}
int main(){
	int choice;
	AMGraph G;
	CreateAdjoin(G);
	cout<<"请选择方式1还是方式2"<<endl;
	cin>>choice;
	switch(choice){
		case 1:{
			TopologicalSort1(G);
			break;
		}
		case 2:{
			TopologicalSort2(G);
			break;
		}
		default:{
			cout<<"你输入的不正确"<<endl; 
			break;
		}
	} 
	
}

总结

其实代码也还好，不难有兴趣的可以尝试一下 反正我确实是一遍打出来了 感觉不错点个赞呗，你都点赞是对作者莫大的鼓舞

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

拓扑排序详解

拓扑排序详解 的相关文章

  • springboot+vue实现增删改查小demo

    学习vue xff0c 就想着自己搭建一个框架学习一下 xff0c 本文属于vue与后台的增删改查入门demo xff0c 不做讲解 xff0c 只为了记录一下代码 后台框架前台框架的搭建自己百度就可以做到了 项目的源码地址 https g

  • JWT(Json web token)

    1 什么是JWT 官网地址 JSON Web Token Introduction jwt io 翻译 jsonwebtoken xff08 JWT xff09 是一个开放标准 xff08 rfc7519 xff09 xff0c 它定义了一

  • MyBatis-plus

    MyBatis plus学习结构图 1 MyBatis plus简介 为什么要学习它呢 MyBatisPlus可以节省我们大量工作时间 xff0c 所有的CRUD代码它都可以自动化完成 JPA tk mapper MyBatisPlus 偷

  • QT制作简易串口

    QT 实现一个简易版串口调试助手 文章目录 1 设计 UI 界面 2 具体代码编写 3 最终实现效果图 一 设计 UI 界面 设计 UI 界面之前 xff0c 让我们先看一下别人设计的串口助手大概长什么样子 xff0c 具体有哪些功能 我们

  • MVC的执行流程

    MVC的执行流程 1 执行服务器2 发送请求到tomcat3 响应客户端总结 1 执行服务器 根据配置创建DispatcherServlet对象 这个对象已创建 xff0c 会根据contextConfigLocation的配置查找spri

  • KVM 虚拟化

    kvm虚拟化 Kvm的安装 KVM下的虚拟机安装和相互访问约束 推荐下载TightVNC 也可以使用 VNCSever 一 虚拟化产品介绍 linux类的虚拟化软件 qemu xff0c 软件纯模拟全虚拟化软件 xff0c 特别慢 xen

  • Linux服务器连接失败，针对ping不通和无法上网问题 CentOS 7

    1 防火墙是否关闭 防火墙关闭命令 xff1a systemctl stop firewalld service 关闭 systemctl start firewalld service 重启防火墙 systemctl disable fi

  • 数据挖掘Java——KNN算法的实现

    一 KNN算法的前置知识 k 近邻 xff08 kNN k NearestNeighbor xff09 是在训练集中选取离输入的数据点最近的k个邻居 xff0c 根据这个k个邻居中出现次数最多的类别 xff08 最大表决规则 xff09 x

  • 数据挖掘Java——DBSCAN算法的实现

    一 DBSCAN算法的前置知识 DBSCAN算法 xff1a 如果一个点q的区域内包含多于MinPts个对象 xff0c 则创建一个q作为核心对象的簇 然后 xff0c 反复地寻找从这些核心对象直接密度可达的对象 xff0c 把一些密度可达

  • 数据挖掘Java——Kmeans算法的实现

    一 K means算法的前置知识 k means算法 xff0c 也被称为k 平均或k 均值 xff0c 是一种得到最广泛使用的聚类算法 相似度的计算根据一个簇中对象的平均值来进行 算法首先随机地选择k个对象 xff0c 每个对象初始地代表

  • Git Bash中怎么复制与粘贴

    git里面的复制粘贴 一 第一种键盘复制粘贴 右击 xff0c 把git bash应用的Options 配置项打开 复制 ctrl 43 insert 粘贴 shift 43 insert 二 第二种鼠标复制粘贴 1 选中你要复制的部分 x

  • 最新版 springboot集成kafka

    在上一篇文章中介绍了怎么在mac系统上搭建kafka xff0c 既然搭建成功了 xff0c 肯定要集成到项目中使用啊 xff0c 但是怎么集成呢 xff0c 这里把我本人集成的代码以及怎么一步步集成的放上来 xff0c 源码也会在本文的后

  • Python循环输出1~100，每10个换一行

    for i in range 1 101 print i end 61 34 34 if i 10 61 61 0 print

  • JavaScript中matches和match方法

    matches 主要是用来判断当前DOW节点是否能完全匹配对应的CSS选择器 xff0c 如果匹配成功 xff0c 返回true xff0c 反之则返回false 语法如下 xff1a element mathces seletor 这个方

  • Row size too large (＞ 8126). Changing some columns to TEXT or BLOB… | Mysql / MariaDB

    Row size too large gt 8126 Changing some columns to TEXT or BLOB Mysql MariaDB 我们最近将客户网站迁移到新服务器 xff0c 并在尝试导入其数据库时遇到以下错误

  • 一文教你完美解决Linux中Unable to locate package xxx问题，解决不了你打我！

    项目场景 xff1a 使用Ubuntu系统进行开发 问题描述 这两天跟着一门网 课学 把html的网页部署到云服务器 xff0c 于是租了个Ubuntu云服务器 xff0c 照着网课的代码去执行 xff0c 然后一直出现这个问题 xff0c

  • Spring相关知识点(全集)

    1Spring概述 1 1Spring概述 1 spring是一个开源框架 2 spring为简化企业级开发而生 xff0c 使用spring xff0c Javabean就可以实现很多以前要考EJB才能实现的功能 同样的功能 xff0c

  • 云服务的三种模式

    1 laaS 基础设施即服务 laaS xff08 Infrastructure as a Service xff09 即基础设施即服务 提供给消费者的服务是对所有计算基础设施的利用 xff0c 包括处理CPU 内存 存储 网络和其他基本的

  • Caused by: java.lang.IllegalStateException: No application config found or it‘s not a valid config!

    复习springboot时遇到的问题 xff0c 找不到application properties 配置文件 xff0c 很奇怪 xff0c 明明放到resource下面了 xff0c 就是编译不进去 xff0c 运行后target根本没

随机推荐

  • Win系统远程桌面连接教程/查询用户名和密码

    要连接的电脑命名为A 被连接的电脑命名为B B电脑 xff1a 右键电脑属性 点击远程设置 点击允许远程连接此电脑 win 43 r打开cmd输入ipconfig查询ip地址 不知道用户名和密码的 输入net user查询用户名 xff0c

  • Tomcat 9.0安装及配置

    目录 一 获取安装包 二 Tomcat9 0 67 环境配置 三 验证 四 补充 一 获取安装包 官网下载https tomcat apache org 解压至英文文件夹下 xff08 路径中需要全英文 xff09 xff0c 记住路径 百

  • 1.Matlab图像的读取和显示

    在开始之前 xff0c 我们需要在脚本里创建个 m文件 xff0c 然后运行 每次运行时要更换至脚本的路径 clc clear closeall 在一个文件的开头经常会看到 那么他们的作用是什么呢 xff1f clc span class

  • 分享一个word转pdf的工具类Aspose[java]

    项目中使用到office文件的格式转换pdf阅读 xff0c 但是没有一款好用的转换工具 由于本人是mac系统 xff0c openoffice也没法使用 xff0c 前期使用itext转换一直中文乱码 xff0c 也没有解决这个问题 xf

  • Window Sever 2012 密码忘记，修改密码的方法

    在VMWare中安装Window Server 2012忘记密码后如何进行破译修复 xff1f 方法如下 xff1a 进入BIOS 设置界面 xff0c 华硕是按f2 xff08 可以查询一下自己相应电脑进入BIOS界面的按键 xff09

  • UNIX环境高级编程笔记

    UNIX环境编程 一 UNIX基础知识1 1 Linux 主要特性1 2 Linux 内核1 3 Linux 目录结构1 4 登录1 登录名2 shell 1 5 输入和输出1 文件描述符2 标准输入 标准输出 标准错误3 不带缓冲的IO4

  • 实现map有序输出

    我们知道golang里的map是无序的 xff0c 不像python里的字典还可以对键值对顺序反序啥的 所以我们下面手动实现map的有序输出 xff0c 其实原理很简单 xff01 package main import 34 fmt 34

  • 三大框架-Spring

    一 概述 spring框架是以一个分层架构 有七个定义良好的模块组成 Spring模块构建在核心容器之上 核心容器定义了创建 配置和管理bean方式 1 Spring Core 核心容器 提供Spring的基本功能 2 SPring Con

  • Java——泛型和Io流

    目录 1 泛型 2 File对象 3 IO流 4 字节输入和输出流 5 缓存流 6 对象流 1泛型 1 1什么是泛型 1 泛型就是限制我们得数据类型 2 为什么使用泛型 我们原来在定义集合时 xff0c 是如下得定义方式 xff1a Lis

  • Spring框架入门学习笔记

    Spring概述 目录 Spring概述 IOC容器 概念 底层原理 Spring提供IOC容器实现两种方式 基于xml方式实现属性注入和对象创建 属性注入 xml注入集合属性 Spring中的bean类型 bean的作用域 bean的生命

  • &和&&的区别?

    amp 和 amp amp 都是Java中的逻辑运算符 xff0c 用于对两个布尔值进行逻辑运算 xff0c 但它们有着不同的特点和使用场景 xff0c 具体区别如下 xff1a 1 运算规则 amp 是按位与运算符 xff0c 它会对两个

  • MAC电脑GOland2022.2.1版本DEBUG问题

    在使用goland使用debug调试代码出现 API server listening at 127 0 0 1 56871 could not launch process debugserver or lldb server not f

  • Maven连接数据库

    1 创建一个maven项目 2 在resources中创建db properties配置文件和log4j properties日志的配置文件 db username 61 root db password 61 root db url 61

  • 关于vs2019网络问题解决方案

    首先将IPV4 的DNS设置为默认的114 114 114 114 xff0c 备用DNS为8 8 8 8 xff0c 若没有用 xff0c 则不勾选IPV6 xff0c 亲测有效 这个问题曾经也困扰了我好几个月 xff0c 甚至都想换掉v

  • Spring Boot启动器

    文章目录 Spring Boot启动器简介自定义springboot启动器命名规约自定义starter步骤1 创建一个Spring boot项目2 导入pom3 编写配置类4 在resources META INF目录下新建spring f

  • web开发入门

    在vscode中输入英文 xff0c 按tab键 xff0c 叩可显示html5的框架 搭建好框架之后 xff0c 再进行局部设计即可制作一张简易静态网页

  • springboot学习笔记

    http t csdn cn aLaeJ

  • spring中的annotation简介

    1 注解介绍 注解 xff0c 是一种用来描述数据的数据 比如说 64 override表示我们重载父类函数 如果我们不用这个注解 xff0c 程序也能执行 xff0c 但是我们加了这个注解代表我告诉编译器这个方法是一个重写的方法 如果父类

  • C语言中如何使用字符数组和字符型指针变量

    案例一 使用字符数组统计字符串的长度以及实现字符串的反转 参考代码 xff1a include lt stdio h gt include lt stdlib h gt include lt string h gt int main cha

  • 拓扑排序详解

    提示 xff1a 古人学问无遗力 少壮功夫老始成 xff0c 纸上得来终觉浅 觉知此事须躬行 文章目录 一 AOV网的特点二 问题三 拓扑排序四 拓扑排序的方法五 检查AOV网中是否存在一个环六 两种思路6 1 思路一6 1 1 思路一代码

热门标签