Read the problem and analysis, read python code 10 - 20 minutes.
http://www.tangjikai.com/algorithms/leetcode-207-208-course-schedule-i-ii
Read Java code later.
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/210.course-schedule-ii.java
Understand the problem and solution quickly through this blog: (10 minutes to read)
http://www.voidcn.com/blog/qq508618087/article/p-5039267.html
Another 10 minutes to read this blog:
http://www.cnblogs.com/grandyang/p/4504793.html
Read 10-20 minutes about graph representation: (11:40am - 12:00pm)
https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs
Spent 20 minutes to watch the video:
https://class.coursera.org/algo-003/lecture
Take some notes:
1. Sink Vertex - concept
2. To compute topological ordering:
- Let v be a sink vertex of G
- set f(v) = n
- recurse on G-{v}
why does it work? when v is assigned to position i
Topological Sort vis DFS
DFS-Loop (graph G)
- mark all nodes unexplored
- current_label = n [to keep track of ordering]
- for each vertex v in set G:
- if v not yet explored [ in some previous DFS call]
- DFS( G, v)
DFS( graph G, start vertex s)
- mark s explored
- for every edge (s, v):
- if v not yet explored
- DFS (G, v)
- Set f(s) = current_label
- current_label --
Read an article: (1:04pm - 1:14pm)
http://www.geeksforgeeks.org/topological-sorting/
Fun part later:
play with visual presentation through the link:
https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html
C# code for Leetcode 210:
https://gist.github.com/jianminchen/5873fc014e806d626807917959e05ea2
update C# code to add the example in the comment, and then, update code to match the example:
https://gist.github.com/jianminchen/85478d1bed0faf4410b76a7af3a48fc3
Question and answer:
What do you
learn today? And what is idea to solve this course schedule problem?
1. First, Julia learned how to do the topological sort, here is an example with its diagram:
The image should be the following: directed edge 0->1, which means that 0 is prerequisite course.
Double check with geekforgeeks article:
Confused since it is the first time to draw the diagram.
So, always
start from nodes with 0 indegree (node 0, node 4).
So, the
ordering can be 0, 1, 2, 3, 4; or 4, 0, 1, 2, 3
2. So, Julia also practices to do some counting for vertex.
vertex 0:
indegree 0, but dependency list: 1, 2, 3
vertex 1:
indegree 1, but dependency list: empty set
...
So, Julia
learns to manage the graph using indegree array for the graph, and dependency
list for each vertex.
3. Julia also learns the easy way to do toplogical sorting using the above graph, and also make the code easy to read, once you remember the graph, you can read the code in 5 minutes.
So, I updated the version of C# code to match this test case:
add explanation variable - line 51:
int[] tmpDep = new int[2] {
prerequisites[i][1] , prerequisites[i][0] };
tmpDep[0] - 0 is the index, similar to
the above diagram node 0, add dependency list: 1, 2, 3
tmpDep[1] - 1 is the index, similar to
the above diagram node 1.
4. Now, understanding one example. Ready to talk about idea of problem solving.
The idea to solve this course schedule problem is first for each vertex to get indegree value and also dependency list.
Do not get confused with dependency.
In above diagram, the directed graph, course 1 should take after course 0, so course 1 is depending on course 0; course 1 has indegree 1 related from course 0. course 0 has no indegree. If course 2, 3 also has to take after course 0, so course 0 has dependency list: 1, 2, 3. If course 0 is dequeue, then, course 0's dependency list: 1, 2, 3, 3 courses' indegree value has to be decremented by one.
Secondly, to find all nodes in the graph with indegree's value 0; put them in the queue {4, 0}, and then, dequeue one by one, add to the result list; and then, each node in the dependency list will decrease the indegree value by 1; and then, if any node is found with 0 indegree value, then, it will be added to the queue as well.
In other words, here are steps:
1. Add nodes
with indegree value 0 to the queue;
2. if queue
is not empty, dequeue one in the front,
add one to the result;
check dependency list one by one,
decrement one on indegree value,
if the node's indegree value is 0, then add to the queue
More reading:
statistics:
Time spent: 5+ hours
No comments:
Post a Comment