Week 10 Flashcards
What is topological order?
Is a linear ordering of vertices such that vertex a precedes vertex b whenever a directed edge e exists from a to b.
When can a topological order be applied?
Can only be applied to directed acyclic graphs (DAG)
If cycles exist, no linear ordering is possible.
What are some applications of topological order?
Taking a sequence of courses given certain course prerequisites.
Scheduling tasks given precedence contraints.
Topological Order
What is a sink/minimal vertex?
A sink of minimal vertex is a vertex with no outgoing edges.
What is the basic idea behind a topological sort?
For i to |V|
* find a sink vertex v;
* num(v) = i;
* remove v and all its incident edges
Or in plain english
* Traverse to first sink
* Output sink
* Remove sink
* Repeat
Topological sort can be implemented using a variant of the recursive depth first traversal. What is its complexity?
Θ (|𝑉| + |𝐸|)
When doing topolgical sort, there are two main approaches. What does it mean for us to do an indegree?
This alternate approach has us starting at the root. Start with the node that has 0 in degree.
This requires a queue.
What is Dijksra’s Algorithm? (Explain generally)
Finds the shortest weighted paths from a single source vertex to all other vertices in a weighted, directed or undirected graph.
* All weights must be non-negative
* Must be a simple graph
When using Dijkstra’s Algorihmn, what we do need to keep track of and how can it be implemented?
For each vertex v, we must keep track of
* whether the vertex still needs to be processed:
* The current distance from the source for the shortest path found so far
* The predecessor vertext for the shortest path found so far.
It can be implemented
* By adding fields to a vertex class
* with parallel arrays (or a table)
What is the complexity of Dijkstra’s Algorithm?
The complexity is 𝑂( |𝑉|^2 ) ordered squared.
The worst case is when we have a complete graph.
What would be the complexity of Dijkstra’s algorithm if we apply it to every vertex as a source?
O(|V|^3)
What would we do in the case that we want to do a Dijkstra’s Algorithm but using negative weights?
In this case we would use Bellman-Ford’s algorithm.
