Key Concepts 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 edges
n 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 black-box algorithms do 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?
asserts if (and only if) an edge is of minimum weight on any cut, then the edge is part of some MST.
This property is used to include edges
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 vs strongly connected
- undirected vs directed
- cycle vs acyclic
- weighted vs unweighted
* positive vs negative weights
What is the Cycle Property?
states if e is the unique heaviest edge in any cycle of G, then e cannot be a part of any MST
This property is used to exclude edges.
