leetcode Graph 图论

本次题解包括

  • 133 Clone Graph
  • 207 Course Schedule
  • 210 Course Schedule II

133. leetcode Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

题目地址: leetcode Clone Graph

题意:给定一张图,要求进行深拷贝

思路:leetcode之前唯一的图。。

用BFS/DFS对图进行遍历,我使用字典(c++叫Map)建立起旧结点和新结点的映射关系,这样就好复制啦。

附上我的测试代码

 


 

207. leetcode Course Schedule

 

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

题目地址: leetcode Course Schedule

题意:给定一些课程,以及他们课程之间先修的关系。如我要修课程1,必须先修完课程0,问是否有可能完成这些课程。

思路:很明显的问题可以转化为求拓扑排序(Topological Sort)

拓扑排序的做法如下:

  1. 每次找入度为0的点,输出该入度为0的点,并删除与之相连接的边
  2. 重复1直到没有入度为0的点。之前输出入度为0的点若小于原图的结点数,那么说明图有环,即拓扑排序不存在,否则即为拓扑排序。

以下面的为例:

Topological Sort

(1) 在(a)图中v0和v1的入度都为0,选择v0并输出,接着删去顶点v0及出边<0,2>,得到的结果如(b)图所示。

(2) 在(b)图中只有一个入度为0的顶点v1,输出v1,接着删去v1和它的三条出边<1,2>,<1,3>和<1,4>,得到的结果如(c)图所示。

(3) 在(c)图中v2和v4的入度都为0,不妨选择v2并输出之,接着删去v2及两条出边<2,3>和<2,5>,得到的结果如(d)图所示。

(4) 在(d)图上依次输出顶点v3,v4和v5,并在每个顶点输出后删除该顶点及出边。

 

C++

 

 

 


 

 

210. leetcode Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

题目地址: leetcode Course Schedule II

题意:和207那题一样,给定各种课程之间依赖关系,求一个满足条件的顺序。

思路:其实就是输出拓扑排序啦~直接上面那题代码改改即可。

 

 

 

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Graph 图论
本文地址:https://www.hrwhisper.me/leetcode-graph/

打赏一杯咖啡钱呗

Leetcode , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *