Graphs Flashcards
bfs,dfs,parethis structure,classification of edges,dags,topicla sortung,scc (21 cards)
what is the pesdocode for BFS
INITIALIZATION
for each vertex u ≠ s:
u.color = WHITE, u.d = ∞, u.π = NIL
s.color = GRAY, s.d = 0, s.π = NIL
Q = empty queue
ENQUEUE(Q, s)
TRAVERSAL
while Q not empty:
u = DEQUEUE(Q)
for each neighbor v of u:
if v.color == WHITE:
v.color = GRAY
v.d = u.d + 1
v.π = u
ENQUEUE(Q, v)
u.color = BLACK # COMPLETION
Initialize BFS
“All vertices WHITE/∞/NIL, start GRAY/0/NIL, enqueue start.
Process queue
Dequeue u, check neighbors, update if WHITE, enqueue, mark u BLACK
“White Distant Nil
for each vertex u ≠ s:
u.color = WHITE, u.d = ∞, u.π = NIL
“Gray Zero Nil Queue” (Start node setup)
s.color = GRAY, s.d = 0, s.π = NIL
Q = empty queue
ENQUEUE(Q, s)
Dequeue, Check, Gray, Update, Enqueue, Black” (Core loop).
while Q not empty:
u = DEQUEUE(Q)
for each neighbor v of u:
if v.color == WHITE:
v.color = GRAY
v.d = u.d + 1
v.π = u
ENQUEUE(Q, v)
u.color = BLACK
what is running time for BFS ?
O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.
see picture in book pg 617.
end result.
when would use BFS?
Shortest Path in Unweighted Graphs
what is the pesdocode for DFS
DFS(G):
1. for each vertex u ∈ G:V // Loop through each vertex in the graph
2. u:color = WHITE // Set the color to white (unvisited)
3. u:π = NIL // No predecessor initially
4. time = 0 // Initialize time counter
5. for each vertex u ∈ G:V // Loop through each vertex again
6. if u:color == WHITE // If the vertex is unvisited
7. DFS-VISIT(G, u) // Start a DFS visit from that vertex
Show the d and values that result from running breadth-first search on the directed graph of Figure 22.2(a), using vertex 3 as the source
When color precedes time i visit
W:for each vertex u ∈ G:V // Loop through each vertex in the graph
C: u:color = WHITE // Set the color to white (unvisited)
P: u:π = NIL // No predecessor initially
T: time =0;
I: for each vertex u ∈ G:V
if u:color == WHITE
V: DFS-Visit(G, u)
what is the pesdocude for DFS-Visit(G,u)
DFS-VISIT(G, u):
1. time = time + 1 // White vertex u has just been discovered
2. u:d = time // Record discovery time of u
3. u:color = GRAY // Mark vertex u as discovered (in progress)
4. for each v ∈ G:Adj[u] // Explore each edge (u, v)
5. if v:color == WHITE // If v is unvisited
6. v:π = u // Set u as the predecessor of v
7. DFS-VISIT(G, v) // Recursively visit v
8. u:color = BLACK // Blacken u; it is finished
9. time = time + 1 // Increment time
10. u:f = time
Time Don’t Get Grumpy. Visit When Processing Finishes.”
Time Don’t Get Grumpy. Visit When Processing Finishes.”
“Time” → Increment the time as soon as you discover u.
“Don’t” → Record the discovery time of u.
“Get” → Set u’s color to GRAY (discovered, in progress).
“Explore” → Explore each neighbor of u.
“Visit” → Check if the neighbor is WHITE, and visit it if it is.
“When” → Set u as the predecessor of v.
“Rain” → Recursively visit the neighbor v.
“Finishes” → Once finished with neighbors, set u’s color to BLACK.
“Finishes” → Increment the time as you finish processing u.
“Finishes” → Record the finish time for u.
what is the running time for DFS ?
O(V + E)
Show the parenthesis structure of the depth-first search of Figure 22.4. pg 632
look at book
what is pesdocode for Toploical sort
TOPOLOGICAL-SORT.G/
1 call DFS.G/ to compute finishing times :f for each vertex
2 as each vertex is finished, insert it onto the front of a linked list
3 return the linked list of vertices
what is running time for toplocoalg sort ?
O(V+E)
lemma: A directed graph G is acyclic if and only if a depth-first search of G yields no back
edges.
what is pesdocde code for sccs
STRONGLY-CONNECTED-COMPONENTS.G/
1 call DFS.G/ to compute finishing times u:f for each vertex u
2 compute GT
3 call DFS.GT/, but in the main loop of DFS, consider the vertices
in order of decreasing u:f (as computed in line 1)
4 output the vertices of each tree in the depth-first forest formed in line 3 as a
separate strongly connected component
