M5: Graphs Flashcards
(27 cards)
What does G = (V, E) mean?
G means graph. V means vertices. E means edges.
Define directed graphs.
A graph where direct matters. (i.e., you can go from A to B, but B may not be directed to A.)
In the context of directed graphs, what do out-degrees mean?
Out degrees refers to the number of edges exiting that node.
(In an adjacency matrix, this would be the number of nodes listed in a ROW)
In the context of directed graphs, what do in-degrees mean?
In degrees refers to the number of edges entering that node.
(In an adjacency matrix, this would be the number of nodes listed in a COLUMNS)
Define a weighted graph
This means the edges have weights. For example, a graph where the edges have associated numbers (i.e., lengths).
How much space does a weighted graph’s adjacency matrix and list take?
Adjacency Matrix: O(V²) space
Adjacency List: O(V + E) space
Define BFS
Breadth-first search. For each node, explore all its neighbors. This is used to find the shortest path in an unweighted graph.
What time does a BFS graph take?
O(V + E)
Write pseudocode for BFS.
BFS(G, s):
for v in G:
color[v] = WHITE, dist[v] = ∞, parent[v] = NIL
color[s] = GRAY, dist[s] = 0, Q = {s}
while Q not empty:
u = dequeue(Q)
for each v in Adj[u]:
if color[v] == WHITE:
color[v] = GRAY
dist[v] = dist[u] + 1
parent[v] = u
enqueue(Q, v)
color[u] = BLACK
Define DFS
Depth first search. For a node, explore all the way down before exploring the other routes. Used for edge classification, cycle detection, and topological sort.
Write pseudocode for DFS
DFS(G):
for v in G:
color[v] = WHITE, parent[v] = NIL
time = 0
for v in G:
if color[v] == WHITE:
DFS-Visit(v)
DFS-Visit(u):
color[u] = GRAY, d[u] = ++time
for v in Adj[u]:
if color[v] == WHITE:
parent[v] = u
DFS-Visit(v)
color[u] = BLACK, f[u] = ++time
What time does a DFS graph take?
O(V + E)
In a directed graph, define a tree edge type.
A tree edge indicates it was discovered by DFS for the first time.
In a directed graph, define a back edge type.
A back edge is an edge that connects back to an ancestor.
In a directed graph, define a forward edge type.
A back edge is an edge that connects to a descendent.
In a directed graph, define a cross edge type.
A cross edge type is an edge that connects two separate branches. An edge that connects two nodes that are neither ancestors nor decedents of each other.
Define Topological Sort
This is when tasks (nodes) are ordered with dependencies. This is only possible for DAGs (Directed Acyclic Graphs).
Input: V = 6, edges = [[2, 3], [3, 1], [4, 0], [4, 1], [5, 0], [5, 2]]
Output: 5 4 2 3 1 0]
The first vertex in topological sorting is always a vertex with an in-degree of 0 (a vertex with no incoming edges). A topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. Another topological sorting of the following graph is “4 5 2 3 1 0”.
Minimum Spanning Tree (MST)
The minimum spanning tree has all the properties of a spanning tree with an added constraint of having the minimum possible weights among all possible spanning trees. Like a spanning tree, there can also be many possible MSTs for a graph.
The number of vertices (V) in the graph and the spanning tree is the same.
There is a fixed number of edges in the spanning tree which is equal to one less than the total number of vertices ( E = V-1 ).
The spanning tree should not be disconnected, as in there should only be a single source of component, not more than that.
The spanning tree should be acyclic, which means there would not be any cycle in the tree.
The total cost (or weight) of the spanning tree is defined as the sum of the edge weights of all the edges of the spanning tree.
There can be many possible spanning trees for a graph.
Define Prim’s algorithm
This is greedy algorithm that creates a MST from a starting vertex. This algorithm always starts with a single node and moves through several adjacent nodes, in order to explore all of the connected edges along the way. At every step, it considers all the edges that connect the two sets and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
Typically uses a min-heap on key values.
What time does Prim’s take?
O(E log V)
Write pseudocode for Prim’s algorithm.
Prim(G, w, r):
for v in G: key[v] = ∞, parent[v] = NIL
key[r] = 0
Q = all vertices
while Q not empty:
u = ExtractMin(Q)
for v in Adj[u]:
if v in Q and w(u,v) < key[v]:
parent[v] = u
key[v] = w(u,v)
Define Kruskal’s algorithm.
In this greedy algorithm, we sort all edges of the given graph in increasing order. Then it keeps on adding new edges and nodes in the MST if the newly added edge does not form a cycle. It picks the minimum weighted edge at first and the maximum weighted edge at last.
Steps:
1.) Sort all the edges in increasing order of their weight.
2.) Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.
3.) Repeat step 2 until there are (V-1) edges in the spanning tree.
What time does Kruskal’s algorithm take?
O(ElogE + ElogV)
Thus: O(E * logE) or O(E*logV)
Write pseudocode for Kruskal’s algorithm.
for v in G: MakeSet(v)
sort edges by weight
for (u,v) in edges:
if FindSet(u) ≠ FindSet(v):
T = T ∪ {(u,v)}
Union(u,v)
