Graphs
The two pieces of a graph
What are vertices and edges?
Both of their running time
What is O(V+E)?
The names of the two algorithms to solve this problem
What are Prim's and Kruskal's?
The names of the three shortest path algorithms
What are topological sort, Dijkstra's, and Bellman-Ford?
Topo sort's running time
What is O(V+E)?
The two representations of a graph in code
What are adjacency list and adjacency matrix?
Algorithm for finding the shortest path from a source vertex to all other vertices in an unweighted graph
What is BFS?
What is the running time of MST algorithms?
Prim's: O(E*log(V))
Kruskal's: O(E*log(E))
We learned algorithms to calculate the shortest part from _____ to ______?
What are a single source and all other vertices?
Name all graph algorithms we've learned that use a regular queue
What are BFS and Bellman-Ford?
When there is a path from every vertex to every other vertex
What is connected?
Uses a queue to store the potential next vertices to visit
What is BFS?
The underlying data structure used in Prim's algorithm
For each of the three algorithms, describe a graph where you cannot use it
topo sort - cycle
Dijkstra's - negative edge weights
Bellman-Ford - negative weight cycle
Spell the shortest path algorithm for a directed graph with non-negative edge weights
What is Dijkstra's?
A graph that is connected and acyclic
What is a tree?
DFS uses a stack or _____ to determine the next vertex to visit
What is recursion?
The underlying data structure in Kruskal's algorithm
What is union-find?
Dijkstra's is most similar to this other algorithm that we've learned this year
What is Prim's?
Topo sort can be described as ______ ______ DFS
What is reverse postorder?
A set of vertices in a graph that are all connected to each other
What is a connected component?
One use of DFS that you cannot use BFS for
What is the difference between lazy and regular Prim's?
Whether you add edges or vertices to the priority queue
What is the best case running time of Bellman-Ford?
O(E)
Sort every algorithm we've learned this semester from lowest to highest run time (there are 7/8)
1. BFS/DFS/Topo sort
2a. Prim's/Dijkstra's
2b. Kruskal's
3. Bellman-Ford