Java-拓扑排序

矫情吗；* 2023-10-09 18:04 17阅读 0赞

说实话我不太明白拓扑是啥东西,拓扑这俩字光是放在这就挺高级的,不过拓扑排序倒挺简单的......

首先简单理解一下概念..假如说有个点A,点A是锁住的,只有先解锁点B 点C 点D才能解锁点A. 那么这个情况的拓扑排序结果就是: B C D A(同一优先级BCD顺序无所谓)

把这个情况拓展一下.. 点A的先决条件是B C,点B的先决条件是D 点C的先决条件是EF 拓扑排序结果即为 EFCDBA(答案不唯一 如调换EF的位置则为FECDB 调换BC的位置则为DBEFCA)

#### 点定义 ####

in是入度 即这个点的先决点有多少个

value 这个点的值

nexts 这个点的所连接的下一个节点 (可有多个)

class Node{
    	int in;
        int value;
    	Node [] nexts;
    }

#### 排序主体 ####

创建一个map保存每个点和它的入度 因为排序的过程需要改这些信息 但是不能直接改元素内的信息

创建zeroQueue队列 每个入度为0的点进队列

for循环把值存在map中 顺便把入度为0的点放进队列(入度为0的点可以直接用)

然后从入度为0的点中拿出一个来查看 把它相连的点入度减1 如果减1之后的点入度为0了 就加入这个zeroQueue

public static List<Node> sort(List<Node> list) {
    	HashMap<Node, Integer> map = new HashMap<Node, Integer>();
    	Queue<Node> zeroQueue = new LinkedList<Node>();
    	for (Node x:list) {
    		map.put(x, x.in);
    		if(x.in==0) {
    			zeroQueue.add(x);
    		}
    	}
    	List<Node> result = new ArrayList<>();
    	while(!zeroQueue.isEmpty()) {
    		Node node = zeroQueue.poll();
    		result.add(node);
    		for(Node x:node.nexts) {
    			map.put(x, map.get(x)-1);//map.put(x, x.in-1);如果这么写就修改了被排序元素(排就排改人家干嘛)
    			if(map.get(x)==0) {
    				zeroQueue.add(x);
    			}
    		}
    	}
    	return result;
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java-拓扑排序

说实话我不太明白拓扑是啥东西,拓扑这俩字光是放在这就挺高级的,不过拓扑排序倒挺简单的...... 首先简单理解一下概念..假如说有个点A,点A是锁住的,只有先解锁点B 点C

矫情吗；*/ 2023年10月09日 18:04/ 0 赞/ 18 阅读

相关拓扑排序

拓扑排序是一张AOV网(Activity Of Vertex NetWork),并且是无环的网! 概念: 设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列V1,V

墨蓝/ 2022年08月05日 13:11/ 0 赞/ 39 阅读

相关拓扑排序（Java实现）

仿照前面那个c++写的，具体思路请看上一个博客，只是用Java实现了一下 class Node\{ public int adjvex; public

阳光穿透心脏的1/2处/ 2022年06月17日 06:25/ 0 赞/ 211 阅读

相关拓扑排序

什么是拓扑排序? 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序

冷不防/ 2022年06月09日 05:57/ 0 赞/ 236 阅读

相关拓扑排序

拓扑排序一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就

小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 258 阅读

相关拓扑排序

（1）有向无环图无环的有向图，简称 DAG (Directed Acycline Graph) 图。有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几

古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 303 阅读

相关拓扑排序

拓扑排序：拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的反

淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 358 阅读

相关拓扑排序

拓扑排序题目做的烦，题解写着玩 [POJ 2762 Going from u to v or from v to u?][POJ 2762 Going from

谁借莪１个温暖的怀抱￠/ 2021年12月20日 16:11/ 0 赞/ 299 阅读

相关拓扑排序 JAVA

判断是否成环 JAVA 代码实现 import java.util.LinkedList; import java.util.Scanner;

爱被打了一巴掌/ 2021年11月09日 23:30/ 0 赞/ 287 阅读

相关拓扑排序

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程

野性酷女/ 2021年09月19日 05:04/ 0 赞/ 467 阅读