算法起步之拓扑排序

简介: 原文: 算法起步之拓扑排序         拓扑排序是图中所有节点的一种线性次序,首先拓扑排序是对有向无环图来说的,如果不满足这个条件则无法拓扑排序,拓扑排序就是遵循一定的规则对节点的排序,规则就是假设在图中有一条边是从a节点出发指向b节点,则在拓扑排序中b节点不可能排在a的前面。
原文: 算法起步之拓扑排序

        拓扑排序是图中所有节点的一种线性次序,首先拓扑排序是对有向无环图来说的,如果不满足这个条件则无法拓扑排序,拓扑排序就是遵循一定的规则对节点的排序,规则就是假设在图中有一条边是从a节点出发指向b节点,则在拓扑排序中b节点不可能排在a的前面。其实就是一直寻找入度为0的节点。我们也可以理解成b的完成必须依赖a的完成,a没有完成则b无法进行,其实这样理解的话我们先前说的线性规划也是一种拓扑排序,像我们平时的起床过程也是一种拓扑排序。


         拓扑排序的实现:

public class TopoSort {
	
	public void topsort(int[][]map){
		int[] into=new int[map.length];
		
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if (map[i][j]==1) {
					into[j]++;
				}
			}
		}
		
		for (int i = 0; i < into.length; i++) {
			int j=0;
			while (into[j]!=0) {
				j++;
				if (j>into.length) {
					return;
				}
			}
			System.out.println(j);
			into[j]=-1;
			for (int k = 0; k < into.length; k++) {
				if (map[j][k]==1) {
					into[k]--;
				}
			}
			
			
		}
		
		
	}

友情提示:转载请注明出处:【作者:idlear  博客:http://blog.csdn.net/idlear】


目录
相关文章
|
5月前
|
算法 C++
【洛谷 P1223】排队接水(贪心算法+结构体排序)
该问题要求安排$n$个人的排队顺序以最小化平均等待时间。每个人接水需时$T_i$,解决方案是让接水时间短的人优先。给定$n\leq1000$和$t_i\leq10^6$,代码示例使用C++实现,通过排序使时间从小到大排列,然后计算平均等待时间。样例输入为10个人的时间数组,输出为优化后的排队顺序及平均等待时间(291.90)。
48 0
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
23天前
|
搜索推荐 Shell
解析排序算法:十大排序方法的工作原理与性能比较
解析排序算法:十大排序方法的工作原理与性能比较
37 9
|
16天前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
17 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
15天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
27 0
|
22天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
55 0
|
3月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
29 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
3月前
|
算法 搜索推荐 Java
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
41 0
|
3月前
|
算法 关系型数据库 MySQL
揭秘MySQL中的版本号排序:这个超级算法将颠覆你的排序世界!
【8月更文挑战第8天】在软件开发与数据管理中,正确排序版本号对软件更新及数据分析至关重要。因MySQL默认按字符串排序版本号,可能出现&#39;1.20.0&#39;在&#39;1.10.0&#39;之前的不合理情况。解决办法是将版本号各部分转换为整数后排序。例如,使用`SUBSTRING_INDEX`和`CAST`函数从`software`表的`version`字段提取并转换版本号,再按这些整数排序。这种方法可确保版本号按逻辑正确排序,适用于&#39;major.minor.patch&#39;格式的版本号。对于更复杂格式,需调整处理逻辑。掌握此技巧可有效应对版本号排序需求。
154 3
|
3月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。