Topological sort题型总结

2024-09-04 14:48
文章标签 总结 sort 题型 topological

本文主要是介绍Topological sort题型总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

拓扑排序是对有向无环图的顶点的一种排序,

  • 检测编译时的循环依赖

  • 制定有依赖关系的任务的执行顺序

拓扑排序的算法是典型的宽度优先搜索算法,其大致流程如下:

  1. 统计所有点的入度,并初始化拓扑序列为空。

  2. 将所有入度为 0 的点,也就是那些没有任何依赖的点,放到宽度优先搜索的队列中

  3. 将队列中的点一个一个的释放出来,放到拓扑序列中,每次释放出某个点 A 的时候,就访问 A 的相邻点(所有A指向的点),并把这些点的入度减去 1。

  4. 如果发现某个点的入度被减去 1 之后变成了 0,则放入队列中。

  5. 直到队列为空时,算法结束,

1. graph怎么构建

Graph 一般是adjecent list,

class DirectedGraphNode {

    int label;

    List<DirectedGraphNode> neighbors;

    ...

}

也可以使用 HashMap 和 HashSet 搭配的方式来存储邻接表

hashmap<Integer, List<Integer>>() 或者HashMap<Integer, HashSet<Integer>>() 来表示;

2.indegree怎么构建

array 或者hashmap<Node, Integer>

3. queue,构建拓扑排序,每次pop 入度为0的node;

首先来个经典的题目: Topological sort;

For graph as follow:

图片

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]

思路:标准topo排序的算法;算indegree,然后每次remove node,neighbor的入度全部减1,以此循环;

/*** Definition for Directed graph.* class DirectedGraphNode {*     int label;*     ArrayList<DirectedGraphNode> neighbors;*     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }* };*/public class Solution {/** @param graph: A list of Directed graph node* @return: Any topological order for the given graph.*/public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {ArrayList<DirectedGraphNode> list = new ArrayList<DirectedGraphNode>();HashMap<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>();for(DirectedGraphNode node: graph) {// node -> neighbor, neighbor indegree + 1 ;for(DirectedGraphNode neighbor: node.neighbors) {if(indegree.containsKey(neighbor)){indegree.put(neighbor, indegree.get(neighbor) + 1);} else {indegree.put(neighbor, 1);}}}Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();for(DirectedGraphNode node: graph) {// if indegree not contains, means indegree is 0;if(!indegree.containsKey(node)){queue.offer(node);}}while(!queue.isEmpty()) {DirectedGraphNode node = queue.poll();list.add(node);for(DirectedGraphNode neighbor : node.neighbors) {indegree.put(neighbor, indegree.get(neighbor) - 1);if(indegree.get(neighbor) == 0) {queue.offer(neighbor);}}}return list;}
}

Course Schedule

[1,0] 代表的物理意义是:0 --> 1 

思路:用hashmap build adjecent list,然后记录indegree,neighbor indegree相互减1.  return count == numCourses.

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {if(prerequisites == null || numCourses < 0) {return false;}int[] indegree = new int[numCourses];HashMap<Integer, List<Integer>> graph = new HashMap<>();for(int i = 0; i < numCourses; i++) {graph.putIfAbsent(i, new ArrayList<>());}for(int[] prerequist : prerequisites) {int course = prerequist[0];int pcourse = prerequist[1];// pcourse -> course;graph.get(pcourse).add(course);indegree[course]++;}Queue<Integer> queue = new LinkedList<>();for(int i = 0; i < numCourses; i++) {if(indegree[i] == 0) {queue.offer(i);}}int count = 0;while(!queue.isEmpty()) {Integer node = queue.poll();count++;for(Integer neighbor: graph.get(node)) {indegree[neighbor]--;if(indegree[neighbor] == 0) {queue.offer(neighbor);}}}return count == numCourses;}
}

Alien Dictionary 思路:从单词之间的关系来得到图的关系, 注意所有的char都是一个node,都是字母;然后用hashmap<Character, HashSet<Character>>来建立图。注意分函数写程序,这样清晰;注意indegree需要把每个node全部赋值为0;然后再进行+1;

class Solution {public String alienOrder(String[] words) {if(words == null || words.length == 0) {return "";}HashMap<Character, HashSet<Character>> graph = new HashMap<>();// 每个character,都得在graph里面建立一个node;for(String word: words) {for(int i = 0; i < word.length(); i++) {graph.putIfAbsent(word.charAt(i), new HashSet<Character>());}}for(int i = 0; i < words.length - 1; i++) {String worda = words[i];String wordb = words[i + 1];int minlen = Math.min(worda.length(), wordb.length());for(int j = 0; j < minlen; j++) {char ac = worda.charAt(j);char bc = wordb.charAt(j);graph.putIfAbsent(ac, new HashSet<Character>());graph.putIfAbsent(bc, new HashSet<Character>());// ac -> bc;if(ac != bc) {graph.get(ac).add(bc);break;}}// 特殊情况return abc -> ab, return "";if(worda.length() > wordb.length() && worda.substring(0, minlen).equals(wordb.substring(0, minlen))) {return "";}}HashMap<Character, Integer> indegree = new HashMap<>();buildIndegree(indegree, graph);Queue<Character> queue = new LinkedList<Character>();StringBuilder sb = new StringBuilder();for(Character node: indegree.keySet()) {if(indegree.get(node) == 0) {queue.offer(node);}}while(!queue.isEmpty()) {Character node = queue.poll();sb.append(node);for(Character neighbor: graph.get(node)) {indegree.put(neighbor, indegree.get(neighbor) - 1);if(indegree.get(neighbor) == 0) {queue.offer(neighbor);}}}return sb.length() == indegree.keySet().size() ? sb.toString() : "";}private void buildIndegree(HashMap<Character, Integer> indegree,HashMap<Character, HashSet<Character>> graph) {// graph的每个node,indegree初始为0;for(Character node: graph.keySet()) {indegree.putIfAbsent(node, 0);}for(Character node: graph.keySet()) {for(Character neighbor: graph.get(node)) {indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1);}}}
}

这篇关于Topological sort题型总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1136281

相关文章

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用

Nginx Location映射规则总结归纳与最佳实践

《NginxLocation映射规则总结归纳与最佳实践》Nginx的location指令是配置请求路由的核心机制,其匹配规则直接影响请求的处理流程,下面给大家介绍NginxLocation映射规则... 目录一、Location匹配规则与优先级1. 匹配模式2. 优先级顺序3. 匹配示例二、Proxy_pa

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li

Linux区分SSD和机械硬盘的方法总结

《Linux区分SSD和机械硬盘的方法总结》在Linux系统管理中,了解存储设备的类型和特性是至关重要的,不同的存储介质(如固态硬盘SSD和机械硬盘HDD)在性能、可靠性和适用场景上有着显著差异,本文... 目录一、lsblk 命令简介基本用法二、识别磁盘类型的关键参数:ROTA查询 ROTA 参数ROTA

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解