COMPSCI 61B Lecture Notes - Lecture 25: Directed Graph, Subroutine, Linked List
Document Summary
Efficient algorithms can improve the performance of code, solve problems that are otherwise intractable. Shows an understanding of how computers work; understand computing. Provides a common platform for interviewing for technical knowledge. You now have a huge toolset you can use to solve problems. Multiple breadth-first searches from vertices of in-degree 0. But not good if we have a new node that points to 7 directly. Go as far as you can get (dfs) Solution: perform a dfs traversal from every vertex with indegree 0, not clearing markings in between traversals. Topological ordering is given by the reverse of that list (reverse postorder) Topological ordering: [2, 5, 6, 0, 3, 1, 4, 7] Can think of this process as sorting our nodes so that they appear in an order consistent with edges. When nodes are sorted in diagram, arrows all point rightwards.
