做ppt配图好用的网站,网站后台维护费用,汕头网页设计制作,分类网站作用今天主要介绍DAG #xff08;Directed acyclic graph#xff09;#xff0c;有向无环图。
无向图的问题相对有向图比较简单#xff0c;比如岛屿问题#xff0c;迷宫问题等。
在有向图中#xff0c;我们通常只关注环是否存在#xff0c;因为有向图中环的存在会让我们的…今天主要介绍DAG Directed acyclic graph有向无环图。
无向图的问题相对有向图比较简单比如岛屿问题迷宫问题等。
在有向图中我们通常只关注环是否存在因为有向图中环的存在会让我们的程序陷入死循环。
举个例子有向图中的方向通常指代一些事情的执行顺序比如说[a, b], [b, c] 我们假设a,b,c是三门课程要学左边的课程之后才能学右边的课程所以这里我们如果要学c就要先学a再学b最后才能学c。 那如果有环【ab】【ba】显然这是矛盾的。 同样。对于一些列复杂的课程 若我们想学5则要先学3要学3则要先学4而要学4则要先学5…这无解 这会让我们DFS的搜索陷入循环。 所以一般我们进行搜索的时候需要判断环是否存在。
另外我们还要提一下【拓扑排序】 刚刚的课程选择问题中是一种优先级限制下的调度问题在有向图中它的定义是 在满足限制条件的情况下如何安排并完成所有任务。 我们可以画出一张有向图顶点对应任务通过数组索引来表示课程有向边对应优先级顺序。 而有向图中的优先级限制下的调度问题等价于【拓扑排序】它的定义是 给定一副有向图将所有的顶点排序使得所有的有向边均从排在前面的顶点指向排在后面的顶点。 如下图 同学可以按照上面排序之后的有向图修完所有课程。
我们利用DFS寻找环
维护一个递归调用期间已访问的顶点的栈Stack若(在递归调用期间通过判断onStack标记数组)两次访问了某个顶点则说明有环若DFS递归调用完毕说明无环。
上面说的还是比较抽象。但是已经大致有一个印象了就是有向无环图因为它的顺序限制原因已经搜索完的点是不可能再次回到它这里的。
具体的我们参考上面拓扑排序的图当搜索到某个点它没有相邻节点它就入栈。 所以最终结果是我们将 最后的课程4放在了栈底最初的课程8放在栈的最顶部。
由于搜索是从随机的点开始的我们将没有相邻节点的点入栈之后再回溯到初始节点将它入栈但是后面的搜索也可能会碰到它。所以要给已经搜索的节点打上标签。
另外要注意一点有些情况下会提示图中无环但是有些题目不会提示所以我们考虑一下再搜索过程中判断是否有环具体的对于某些节点X我们搜索过但是因为我们还没找到那个没有相邻节点的点end或者我们还没有从end回溯到X那么此时X节点的状态就是【搜索中】如果我们搜索的过程中两次搜索到X那说明到X节点的图不是单向的而是存在一个环。
所以我们将节点分类为【搜索中】【已搜索】【未搜索】 假设有一对相邻节点uv方向是u到 v 。 我们从u开始搜索此时需要判断v的状态 【v是未搜索】那我们可以搜索v搜索完成之后回溯到u 。 【v是搜索中】那表示有一个环经过了v节点这种情况下不存在拓扑排序。 【v是已搜索】那v已经入栈了而u不在栈中那么u入栈就和v没关系只看u自己的其他相邻节点来决定它的入栈时间即可。
下面用题目演示更直白
LeetCode 210 课程表II
https://leetcode.cn/problems/course-schedule-ii/
现在你总共有 numCourses 门课需要选记为 0 到 numCourses - 1。
给你一个数组 prerequisites 其中 prerequisites[i] [ai, bi]
表示在选修课程 ai 前 必须 先选修 bi 。例如想要学习课程 0 你需要先完成课程 1 我们用一个匹配来表示[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序你只要返回 任意一种 就可以了。如果不可能完成所有课程返回 一个空数组 。实例1
输入numCourses 2, prerequisites [[1,0]]
输出[0,1]
解释总共有 2 门课程。要学习课程 1你需要先完成课程 0。因此正确的课程顺序为 [0,1] 。实例2
输入numCourses 4, prerequisites [[1,0],[2,0],[3,1],[3,2]]
输出[0,2,1,3]
解释总共有 4 门课程。要学习课程 3你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。实例3
输入numCourses 1, prerequisites []
输出[0]import collections
class Solution:def findOrder(self, numCourses: int, prerequisites: List[List[int]]) - List[int]: edges collections.defaultdict(list) # 有向图的表达方式for x in prerequisites:edges[x[1]].append(x[0]) # 每个点 和 它能到的相邻节点has_circle False #是否包含环res [] # 栈底是没有相邻节点的点栈顶是源点返回res[::-1]state [0]*numCourses# 0 1 2 代表未搜索 搜索中已搜索def dfs(current):nonlocal has_circle # nonlocal函数之外定义函数之内改变值state[current]1for v in edges[current]:if state[v] 1:has_circleTruereturnelif state[v] 0:dfs(v)if has_circle:returnelse:continue state[current]2 # 每次的dfs会添加一个节点到栈底这个节点没有指向任何节点res.append(current)for i in range(numCourses):if not has_circle and not state[i]:dfs(i)if has_circle:return []return res[::-1]LeetCode 207 课程表
https://leetcode.cn/problems/course-schedule/
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。示例 1输入numCourses 2, prerequisites [[1,0]]
输出true
解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。
示例 2输入numCourses 2, prerequisites [[1,0],[0,1]]
输出false
解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。
解答方法就是判断这个有向图中有没有环。比上一题更简单。 class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) - bool:# 不能完成的几个情况 # 图中有环自相矛盾import collectionsedges collections.defaultdict(list)for x in prerequisites:edges[x[1]].append(x[0])state [0]*numCourses # 0 1 2 未搜索 搜索中 已搜索has_circle False# res_stack []def dfs(u):nonlocal has_circlestate[u]1for v in edges[u]:# print(v, state)if state[v]0:dfs(v)if has_circle:return elif state[v] 1:has_circleTruereturnelse:continuestate[u]2# res_stack.append()for i in range(numCourses):if not has_circle and not state[i]:dfs(i)if has_circle:return Falsereturn True
