These are all the cards combined Flashcards
What is a DAGs?
Directed, Acyclic Graphs
What are Strongly Connected Components?
subsets of vertices in a directed graph such that there is a directed path from any vertex in the subset to every other vertex in the same subset.
What are Sources?
In a directed graph, a source is a vertex in a directed graph that has no incoming edges.
What are Sinks?
In a directed graph, a sink is a vertex in a directed graph that has no outgoing edges.
What are Trees?
is a specific type of undirected graph that is connected and acyclic.In a directed graph, each vertex, except the root, has one incoming edge (from its parent) and may have multiple outgoing edges (to its children). The tree will be acyclic.
What is a MST?
MST is Minimum Spanning Tree. a connected, undirected graph is a tree that spans all the vertices of the graph, with the minimum possible total edge weight
What are Flow Networks?
is a directed graph in which each edge has a capacity and a flow
In runtime, O(m+n), what does m signify and what does n signify?
m signify edgesn signify vertices
In runtime O(C m), what does C signify?
Size of the max flow
What algorithm does Ford-Fulkerson use internally?
DFS
What algorithm does SCC use internally?
2 DFS
What algorithm does Edmond-Karp use internally?
BFS
Why would use Djistra’s over Belman Ford and Floyd Warshall?
Dijkstra’s are more efficient for postive weights only.
Why would use Belman Ford and Floyd Warshall over Djikstra’s?
Bellman Ford and Floyd Warshall works on negative weights, whereas Djikstra’s does not.
Why would you use Floyd Warshall over Bellman Ford?
Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex.
Why would you use Bellman Ford over Floyd Warshall ?
Floyd Warshall is good for finding shortest path from all vertices, whereas Bellman Ford is only good for finding shortest path from 1 vertex to all other vertices.
Why would you choose Kruskal’s over Prim or vice versa?
It does not matter which algorithm you use. Choose one which is easier to remember. Reference: https://edstem.org/us/courses/50892/discussion/4313106?comment=10048285
Why would you use DFS over BFS or vice versa?
BFS is good for finding the shortest path for unweighted graphs from a starting vertex using dist(u). DFS is good at topologically sorting a DAG and finding connected components.
Do Kruskal’s and Prims algorithm work on directed and undirected graphs?
No. They don’t work on directed graphs.
Why would you choose Explore over DFS?
Explore takes a starting vertex as an input. Explore only visits all reachable vertices from the starting vertex. We’ll get a visited array with reachable vertices marked as TRUE and non-reachable vertices marked as FALSE. whereas DFS explores all vertices regardless if they are reachable from the starting vertex. The visited array for DFS will always return TRUE for all vertices.
What is the Cut Property?
if edges X are part of a minimum spanningtree of graph G, we can pick any subset of nodes S for which X doesnot cross between S and V-S, and let e be the lightest edge acrossthis partition. Then X U {e} is a part of some MST.
What is the difference between Ford-Fulkerson and Edmonds-Karp algorithm?
Edmonds-Karp only needs positive capacities whereas Ford-Fulkerson requires positive integer capacities.
What are the different types of graphs?
- connected vs disconnected* undirected vs directed* cycle vs acyclic* weighted vs unweighted * positive vs negative weights
What is the runtime of:DFS Runtime
O(n+m)
What is the runtime of:Explore Runtime
O(n+m)
What is the runtime of:BFS Runtime
O(n + m)
What is the runtime of:SCC Runtime
O( (m+n) log n)O(m log n) if strongly connected
What is the runtime of:Bellman Ford
O(nm)
What is the runtime of:Floyd Warshall
O(n^3)
What is the runtime of:Kruskal’s
(m log n)
What is the runtime of:Prims
O(m log n)
What is the runtime of:2-SAT
O(n+m)
What is the runtime of:Ford Fulkerson
O(C m)
What is the runtime of:Edmonds-Karp
O(nm^2)
What is the runtime of:Explore on an undirected graph
O(m+n) simplifies to O(m)
What is the runtime of:DFS on a connected graph
O(m+n) simplifies to O(m)
What is the runtime of:Explore on connected MST
O(m+n)
What is the runtime of:DFS on unconnected MST
O(m+n)
What is the runtime of:traversing a full graph
O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:reversing a full graph
O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:copying a full graph
O(m+n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:iterating, checking, reading, removing, working on all vertices (or subset)
O(n)Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:checking, reading, or removing one edge
O(n) or O(m)Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:iterating, checking, reading, removing, working on all edges
O(n+m)
What is the runtime of:Running an O(m+n) black-box algorithm on a MST which is connected
O(m)
What is the runtime of:Running an O(m+n) black-box algorithm on a Max Flow which is connected
O(m)
What is the runtime of:Accessing an edge property such as a weight
O(1)
Name graph algorithms that are used for:Traversing a Graph
DFS, Explore, BFS
Name graph algorithms that are used for:Getting Components
SCC
Name graph algorithms that are used for:Getting Shortest Paths
Dijkstra’s, Bellman Ford, Floyd Warshall
Name graph algorithm that are used for:Finding MSTs
Kruskal’s, Prims
Name graph algorithm that are used for:finding an existing path
2-SAT
Name graph algorithms that are used for: Finding the Max Flow
Ford-FulkersonEdmonds-Karp
What is the best algorithm for determining the shortest path of graph G that is weighted with positive weights?
Djikstra’s
What are the best algorithms for determining the shortest path of graph G that is weighted with negative weights?
Bellman Ford or Floyd Warshall
What are the best algorithms for determining the best capacity?
Ford-Fulkerson and Edmonds-Karp
What is the best algorithm to convert a graph to a topologically sorted DAG?
SCC
What is the best algorithm to find the shortest path from all vertices of a directed, weighted graph with negative weights?
Floyd Warshall
What is the best algorithm to find the shortest path from a given vertex of a directed, weighted graph with negative weights?
Bellman Ford
DFS: What is the input, output, and variables we have access to?
Input: G = (V, E) Output:* A topological sort on a DAG* undirected graph: ccnum (connected component number)* directed graph: a list of connected componentsAccess to:* prev array* pre array* post array
Explore: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* visited(u) - visited array which is set to TRUE for all vertices reachable from vAccess to:* ccnum array (ccnum[])* previously visited array (visited[]) * An array of vertices before a given vertex. * Used by Explore and required for DFS.
BFS: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* dist[] - for all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.Access to:* prev[] - vertex preceding u in shortest path from v to reachable vertex u
Djikstra’s: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* dist[] - for all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.Access to:* prev[] - vertex preceding u in shortest path from v to reachable vertex u
Bellman Ford: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Start vertex v in VOutput:* The shortest path from vertex s to all other vertices.Access to:* Detect negative weight cycles. We can compare T[n, *] to T[n - 1, *]. * We can only find negative weight cycles that can be reached from starting vertex s.
Floyd-Warshall: What is the input, output, and variables we have access to?
Input:* G = (V, E)Output:* The shortest path from all vertices to all other verticesAccess to:* We can detect negative weight cycles by checking the diagonals (T[n, i, i]).
SCC: What is the input, output, and variables we have access to?
Input:* G = (V, E)Output:* meta-graph (DAG) that contains the connected components* Topological sorting of the meta-graph * With a source SCC first and a sink SCC lastAccess to:* ccnum[] - strongly connected components produced from the 1st DFS run
Kruskal’s: What is the input, output, and variables we have access to?
Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the edges E
Prim: What is the input, output, and variables we have access to?
Input:* Connected, Undirected Graph G = (V, E) with edge weights w_eOutput:* An MST defined by the prev[] array
2-SAT: What is the input, output, and variables we have access to?
Input:* A Boolean formula in 2-CNF is represented as a set of clauses where each clause is a disjunction of exactly two literals.Output:* A Boolean value indicates whether the given 2-CNF formula is satisfiable. If it is satisfiable, the algorithm may also provide a satisfying assignment of variables.
Ford-Fulkerson: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Flow capacity c* Source node s* Sink node tOutput:* Max FlowAccess to:* Can trivially create the final residual network with G* Max flow of G
Edmonds-Karp: What is the input, output, and variables we have access to?
Input:* G = (V, E)* Flow capacity c* Source node s* Sink node tOutput:* Max FlowAccess to:* Can trivially create the final residual network with G* Max flow of G
