您现在的位置是:首页 >  企业信息化 > 操作系统 > 其他其他

leetcode 207. 课程表---拓扑排序篇一

2021-06-07 21:00:47其他人已围观

简介课程表题解集合引言拓扑排序二级目录三级目录引言本题涉及到了拓扑排序相关的概念,如果对拓扑排序不了解的,建议看这篇文章AOV网与拓扑排序拓扑排序二级目录三级目录

在这里插入图片描述
在这里插入图片描述

课程表题解集合

  • 引言
  • 拓扑排序----BFS
  • DFS


引言

本题涉及到了拓扑排序相关的概念,如果对拓扑排序不了解的,建议看这篇文章AOV网与拓扑排序


拓扑排序----BFS

图解:
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
拓扑排序实际上应用的是贪心算法。贪心算法简而言之:每一步最优,全局就最优。

具体到拓扑排序,每一次都从图中删除没有前驱的顶点,这里并不需要真正的做删除操作,我们可以设置一个入度数组,每一轮都输出入度为 0 的结点,并移除它、修改它指向的结点的入度(−1即可),依次得到的结点序列就是拓扑排序的结点序列。如果图中还有结点没有被移除,则说明“不能完成所有课程的学习”。

拓扑排序保证了每个活动(在这题中是“课程”)的所有前驱活动都排在该活动的前面,并且可以完成所有活动。拓扑排序的结果不唯一。拓扑排序还可以用于检测一个有向图是否有环。相关的概念还有 AOV 网,这里就不展开了。

算法流程:

1、在开始排序前,扫描对应的存储空间(使用邻接表),将入度为 0 的结点放入队列。

2、只要队列非空,就从队首取出入度为 0 的结点,将这个结点输出到结果集中,并且将这个结点的所有邻接结点(它指向的结点)的入度减 1,在减 1 以后,如果这个被减 1 的结点的入度为 0 ,就继续入队。

3、当队列为空的时候,检查结果集中的顶点个数是否和课程数相等即可。

思考这里为什么要使用队列?(马上就会给出答案。)

在代码具体实现的时候,除了保存入度为 0 的队列,我们还需要两个辅助的数据结构:

1、邻接表:通过结点的索引,我们能够得到这个结点的后继结点;

2、入度数组:通过结点的索引,我们能够得到指向这个结点的结点个数。

这个两个数据结构在遍历题目给出的邻边以后就可以很方便地得到。

代码:

class Solution {
public:
	//a[0]=1--->学习0,需要先学习1: 1---->0
	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
	{
		//入度数组----记录学习每门学科前需要学习几门其他的学科
		vector<int> inDegree(numCourses, 0);
		//邻接表-----学习完当前课程后,能够去学习其他什么课程
		vector<vector<int>> rej(numCourses);
		//计算入度数组和邻接表
		for (auto p : prerequisites)
		{
			//想要学习学科p[0],需要先去学习学科p[1]
			//对应关系为---p[1]--->p[0]
			inDegree[p[0]]++;
			rej[p[1]].push_back(p[0]);
		}
		queue<int> q;
		//将入度为0的点入队
		for (int i = 0; i < numCourses; i++)
		{
			if (inDegree[i] == 0)
			{
				q.push(i);
			}
		}
		//记录已经出队的课程数量
		int cnt = 0;
		while (!q.empty())
		{
			//获取队头
			int front = q.front();
			q.pop();
			cnt++;
			//检查队头的后继节点,将其后继节点入度减去一
			for (auto p : rej[front])
			{
				//判断入度减去一后,后继节点的入度数量是否为0,如果为0,就入队
				if (--inDegree[p] == 0) q.push(p);
			}
		}
		//如果无环存在,那么所有课程都会出队一次,否则,存在环
		return cnt == numCourses;
	}
};

在这里插入图片描述
这里回答一下使用队列的问题,如果不使用队列,要想得到当前入度为 0 的结点,就得遍历一遍入度数组。使用队列即用空间换时间。


DFS

原理是通过 DFS 判断图中是否有环。

算法流程:

  1. 借助一个标志列表 flags,用于判断每个节点 i (课程)的状态:

    未被 DFS 访问:i == 0;

    已被其他节点启动的 DFS 访问:i == -1;

    已被当前节点启动的 DFS 访问:i == 1。

  2. 对 numCourses 个节点依次执行 DFS,判断每个节点起步 DFS 是否存在环,若存在环直接返回 False。DFS 流程;

    终止条件:

    当 flag[i] == -1,说明当前访问节点已被其他节点启动的 DFS 访问,无需再重复搜索,直接返回 True。

    当 flag[i] == 1,说明在本轮 DFS 搜索中节点 i 被第 2 次访问,即 课程安排图有环 ,直接返回 False。

    将当前访问节点 i 对应 flag[i] 置 1,即标记其被本轮 DFS 访问过;

    递归访问当前节点 i 的所有邻接节点 j,当发现环直接返回 False;

    当前节点所有邻接节点已被遍历,并没有发现环,则将当前节点 flag 置为 -1 并返回 True。

  3. 若整个图 DFS 结束并未发现环,返回 True。

简而言之:

第 1 步:构建逆邻接表;

第 2 步:递归处理每一个还没有被访问的结点,具体做法很简单:对于一个结点来说,先输出指向它的所有顶点,再输出自己。

第 3 步:如果这个顶点还没有被遍历过,就递归遍历它,把所有指向它的结点都输出了,再输出自己。注意:当访问一个结点的时候,应当先递归访问它的前驱结点,直至前驱结点没有前驱结点为止。

图解:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码:

class Solution {
public:
	//a[0]=1--->学习0,需要先学习1
	bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
	{
		//逆邻接表---记录学习每一门课程前需要学习的课程
		vector<vector<int>> res(numCourses);
		//p[1]---->p[0]
		for (int i = 0; i <prerequisites.size(); i++)
			res[prerequisites[i][1]].push_back(prerequisites[i][0]);
		//标记数组,标记当前课程是正在访问,还是已经访问过了
		vector<int> marked(numCourses, 0);
		//递归处理每一个还没有被访问的结点,具体做法很简单:对于一个结点来说,先输出指向它的所有顶点,再输出自己。
		for (int i = 0; i < numCourses; i++)
		{
			// 注意方法的语义,如果图中存在环,表示课程任务不能完成,应该返回 false
			if (dfs(i, res, marked)) return false;
		}
		// 在遍历的过程中,一直 dfs 都没有遇到已经重复访问的结点,就表示有向图中没有环
	// 所有课程任务可以完成,应该返回 true
		return true;
	}
	/**
	 * 注意这个 dfs 方法的语义
	 * @param i      当前访问的课程结点
	 * @param graph
	 * @param marked 如果 == 1 表示正在访问中,如果 == 2 表示已经访问完了
	 * @return true 表示图中存在环,false 表示访问过了,不用再访问了
	 */
	bool dfs(int i, vector<vector<int>>& graph, vector<int>& marked)
	{
		// 如果访问过了,就不用再访问了

		// 从正在访问中,到正在访问中,表示遇到了环
		if (marked[i]==1) return true;
		//表示在访问的过程中没有遇到环,这个节点访问过了
		if (marked[i] == 2) return false;
		// 走到这里,是因为初始化呢,此时 marked[i] == 0
	   // 表示正在访问中
		marked[i] = 1;
		//遍历学习当前课程前需要学习的课程
		for (auto gra : graph[i])
		{
			// 层层递归返回 true ,表示图中存在环
			if (dfs(gra, graph, marked)) return true;
		}
		// i 的所有后继结点都访问完了,都没有存在环,则这个结点就可以被标记为已经访问结束
	   // 状态设置为 2
		marked[i] = 2;
		// false 表示图中不存在环
		return false;
	 }
};

在这里插入图片描述
复杂度分析:

  • 时间复杂度:O(E + V);
  • 空间复杂度:O(E + V)。

文章来源:https://blog.csdn.net/m0_53157173/article/details/117586858

Tags:

很赞哦! ()

随机图文

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计247968篇文章
  • 浏览统计18356次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们