Exam 2 - Graphs Flashcards
What algorithm would I use to topologically sort a DAG?
DFS
What algorithm would I use to find all of the connected components in a graph?
DFS
Can DFS be used on directed graphs or undirected graphs?
It can be used on both
Can DFS be used on DAGs
Yes
What is the runtime of DFS?
O(n+m)
What are the inputs of DFS?
G = (V,E)
What are the outputs of DFS?
ccnum[] the array of connected component numbers
prev[] the previous array which can be used for backtracking to find a path
pre[] the preorder numbers for each vertex
post[] the postorder numbers for each vertex, which can be used for topological sorting
What algorithm can I use to find which nodes are reachable from S?
Explore subroutine
What are the inputs of the Explore subroutine?
G = (V,E)
Starting vertex v from V
What is the output of the Explore subroutine?
visited[]
array of vertices reached before a given vertex
true for all vertices reachable from v
What is the runtime of the Explore subroutine?
O(m+n)
Can you use BFS on a graph with edge weights?
No
What kind of graphs can BFS be used on?
Unweighted, both directed and undirected
What are the inputs of BFS?
G = (V,E)
Start vertex v from V
What does BFS do?
Performs a breadth-first search of the graph from a starting vertex, finding the number of edges from v to any other vertex
What are the outputs of BFS?
dist[] for all vertices u reachable from v, dist[u] is the length of the number of edges in the shortest path from v to u – infinite if unreachable
prev[] vertex preceding u in the shortest path from v to reachable vertex u
What is the runtime of BFS?
O(m+n)
What graph trait can Dijkstra’s algorithm not handle?
Negative edge weights
What algorithm would I use to find the shortest distance from a source vertex to all other vertices in a graph with nonnegative edge weights?
Dijkstra’s algorithm
What are the inputs to Dijkstra’s algorithm?
G = (V,E)
Start vertex v in V
w_e for e in E, non negative weights
What are the outputs of Dijkstra’s algorithm?
dist[] shortest distance between vertex v and reachable vertex u, or infinity if not reachable
prev[] vertex preceding u in the shortest path from v to reachable vertex u
What is the runtime of Dijkstra’s algorithm?
O((m+n) log n)
What algorithm would I use if I wanted to find the shortest distance from a source vertex to all other vertices in a graph that may contain negative edge weights?
Bellman-Ford
What are the inputs to the Bellman-Ford algorithm?
G = (V,E)
Start vertex s in V
w_e for e in E
What is the output of the Bellman-Ford algorithm?
Shortest path from vertex s to all other vertices
How does the Bellman-Ford algorithm detect negative weight cycles that can be reached from starting vertex s?
Comparing the last iteration T[n,] to T[n-1,] and seeing if any distances got shorter despite not exploring any further
What is the runtime of the Bellman-Ford algorithm?
O(m*n)
What algorithm would I use if I wanted to find the shortest path from all vertices to all other vertices in a graph?
Floyd-Warshall
Does Floyd-Warshall allow negative weights?
Yes
What are the inputs of the Floyd-Warshall algorithm?
G = (V,E)
w_e for e in E
What is the output of the Floyd-Warshall algorithm?
The shortest path from all vertices to all other vertices
How does the Floyd-Warshall algorithm detect negative weight cycles?
Checking the diagonals T[n, i, i] to see if any vertex has a path shorter than zero to itself
What is the runtime of the Floyd-Warshall algorithm?
O(n^3)
What is the output of the Strongly Connected Components algorithm?
Metagraph (DAG) containing the strongly connected components
A topological sorting of the metagraph, with source SCCs first, and sink SCCs last
Also the connected component number array from the first DFS run in the algorithm
Can the SCC algorithm be used on undirected graphs?
No, directed graphs don’t have strongly connected components
What is the runtime of the SCC algorithm?
O(m+n)
What algorithm would I use to find an MST, using a union-find data structure?
Kruskal’s algorithm
What algorithm would I use to find an MST, using a fibonacci heap?
Prim’s algorithm
What are the inputs to Kruskal’s/Prim’s algorithms?
Connected, undirected graph G = (V,E)
w_e edge weight for each e in E
What is the output of Kruskal’s algorithm?
An MST, defined by edges from E
What is the output of Prim’s algorithm?
An MST, defined by the prev[] array
What is the runtime of Kruskal’s/Prim’s algorithms?
O(m log n)
What kinds of graphs can Kruskal’s/Prim’s algorithms be used on?
Connected, undirected, weighted graphs
What does the 2-SAT algorithm do?
Takes a CNF with all clauses of size <= 2 and returns a satisfying assignment if it exists
What is the input of the 2-SAT algorithm?
A 2-CNF boolean formula
What is the output of the 2-SAT algorithm?
Whether the input formula can be satisfied, and if it can, what values satisfy it.
How does the 2-SAT algorithm work?
It uses a directed graph to represent implications from the formula, and then checks the SCCs to see if there are any contradictions.
What is the runtime of the 2-SAT algorithm?
O(m + n)
m is number of clauses
n is number of variables
What algorithm would I use to find the max flow of a network with integer edge capacities?
Ford-Fulkerson
Which algorithms have we covered that are greedy algorithms?
Ford-Fulkerson and Edmonds-Karp
What are the inputs to the Ford-Fulkerson and Edmonds-Karp algorithms?
G = (V,E)
Flow capacity c for all edges
Source node s
Sink node t
What are the outputs of the Ford-Fulkerson and Edmonds-Karp algorithms?
The maximum flow, and effectively the residual network because it can easily be recreated with G and the max flow
What algorithm would I use to find the max flow of a network with noninteger edge capacities?
Edmonds-Karp
How is Edmonds-Karp different from Ford-Fulkerson?
It uses BFS instead of DFS
What is the runtime of Ford-Fulkerson?
O(C*m)
C is maximum flow of network
m is number of edges
What is the runtime of Edmonds-Karp?
O(n * m ^ 2)
n is number of vertices
m is number of edges
When should I choose Ford-Fulkerson over Edmonds-Karp?
When we know the weights are integers and we know the maximum weight size is limited
What is the adjacency matrix representation of a graph?
An n x n matrix (where n is number of vertices) containing either true or false at each entry, where an entry at u,v represents whether there exists an edge from u to v
What is the adjacency list representation of a graph?
A linked list for each vertex, holding the ids of the vertices that it has an outgoing edge to
What is a tree edge?
An edge that was created when visiting an unexplored vertex
What is a forward edge?
An edge that leads from a node to a nonchild descendant
What is a back edge?
An edge that leads to an ancestor
What is a cross edge?
An edge that leads to a previously completely explored node that is neither a descendant nor an ancestor
Graph G has a cycle if its DFS tree has a ____ edge
back
