拓扑排序(leetcode 207、210)

2024-06-20 09:08
文章标签 leetcode 排序 210 拓扑 207

本文主要是介绍拓扑排序(leetcode 207、210),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

拓扑排序

有向无环图

有向无环图:无环的有向图,简称DAG(Directed Acycline Graph)。

有向无环图的应用

有向无环图常用来描述一个工程或系统的进行过程(通常把计划、施工、生产、程序流程等当成一个工程)。
一个工程可以分为若干个子工程,只要完成了这些子工程(活动),就可以使得整个工程完成。
有向无环图分为两种表示方法,AOV网与AOE网。

AOV网 (拓扑排序)

用一个有向图表示一个工程的各个工程及其互相制约关系,其中顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动网,简称AOV(Activity On Vertex network)。

AOE 网(关键路径)

用一个有向图表示一个工程的各个子工程及其互相制约关系,以弧表示活动,以顶点表示获得开始或结束事件,称这种有向图为边表示活动的网,简称AOE 网(Activity On Edge)。
下篇文章具体再进行介绍

AOV网的特点

  • 若从i到j有一条有向路径,则i是j的前驱,j是i的后继。
  • 若<i,j> 是网中有向边,则i是j的直接前驱,j是i的直接后继。
  • AOV网中不允许有回路,因为如果有回路存在,则表示某项活动以自己为先决条件,显然这是荒谬的。

拓扑排序

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

拓扑排序的方法

  1. 在有向图中选一个没有前驱的顶点且输出值
  2. 从图中删除该顶点和所有以它为尾的弧。
  3. 重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点位置。

问题:如何判别AOV网中是否存在回路?

对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网必定不存在环。

邻接矩阵表示图进行拓扑排序

两道leetcode相关题

207. 课程表

/**
* 邻接矩阵表示的图的拓扑排序,广度优先
*/
bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize){//入度int *indgree = (int *)calloc( numCourses, sizeof(int) );//邻接矩阵存储int ** graph = (int **)calloc( numCourses, sizeof(int *) );for ( int i = 0; i < numCourses; i++ ) {graph[i] = (int *)calloc( numCourses, sizeof(int) );}//统计入度for ( int i = 0; i < prerequisitesSize; i++ ) {graph[prerequisites[i][1]][prerequisites[i][0]] = 1;indgree[prerequisites[i][0]]++; }//打印邻接矩阵// for (int i = 0; i < numCourses; i++ ) {//     for (int j = 0; j < numCourses; j++) {//         printf("%4d", graph[i][j]);//     }//     printf("\n");// }// 打印入度// for ( int i = 0; i < numCourses; i++ ) {//     printf("%4d", indgree[i]);// }// printf("\n");int *queue = (int *) calloc(numCourses, sizeof(int));int head = 0, tail = 0;// //寻找入度为0的入队for ( int i = 0; i < numCourses; i++ ) {if ( indgree[i] == 0 ) {queue[tail++] = i;}}// // 队列不为空while ( head < tail ) {int node = queue[head++]; //出队for (int j = 0; j < numCourses; j++ ) { //遍历if ( graph[node][j] == 1 ) { //寻找以node课程为先学的课程if ( --indgree[j] == 0 ) { //关联节点的入度为0的时候继续加入队列queue[tail++] = j;}}}}if ( tail != numCourses ) { //如果全部入队,则表示肯定可以完成return false;}//如果成功,则伪队列的存放的顺序即为一个拓扑序列// for (int i = 0 ; i < numCourses; i++) {//     printf("%4d", queue[i]);// }// printf("\n");return true;
}

210. 课程表 II

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize){//入度int *indgree = (int *)calloc( numCourses, sizeof(int) );//邻接矩阵存储int ** graph = (int **)calloc( numCourses, sizeof(int *) );for ( int i = 0; i < numCourses; i++ ) {graph[i] = (int *)calloc( numCourses, sizeof(int) );}//统计入度for ( int i = 0; i < prerequisitesSize; i++ ) {graph[prerequisites[i][1]][prerequisites[i][0]] = 1;indgree[prerequisites[i][0]]++; }//打印邻接矩阵// for (int i = 0; i < numCourses; i++ ) {//     for (int j = 0; j < numCourses; j++) {//         printf("%4d", graph[i][j]);//     }//     printf("\n");// }// 打印入度// for ( int i = 0; i < numCourses; i++ ) {//     printf("%4d", indgree[i]);// }// printf("\n");int *queue = (int *) calloc(numCourses, sizeof(int));int head = 0, tail = 0;// //寻找入度为0的入队for ( int i = 0; i < numCourses; i++ ) {if ( indgree[i] == 0 ) {queue[tail++] = i;}}// // 队列不为空while ( head < tail ) {int node = queue[head++]; //出队for (int j = 0; j < numCourses; j++ ) { //遍历if ( graph[node][j] == 1 ) { //寻找以node课程为先学的课程if ( --indgree[j] == 0 ) { //关联节点的入度为0的时候继续加入队列queue[tail++] = j;}}}}free(indgree);free(graph);if ( tail != numCourses ) { //如果全部入队,则表示肯定可以完成free(queue);*returnSize = 0;return NULL;}//如果成功,则伪队列的存放的顺序即为一个拓扑序列// for (int i = 0 ; i < numCourses; i++) {//     printf("%4d", queue[i]);// }// printf("\n");*returnSize = numCourses;return queue;
}

这篇关于拓扑排序(leetcode 207、210)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点