Understanding Breadth-First Search (BFS) Algorithm for Graph Searching
This content delves into the Breadth-First Search (BFS) algorithm, a fundamental graph searching technique. It explains the step-by-step process of BFS, from initializing the graph to traversing vertices in a specific order. Through detailed visual representations, you will gain insights into how BFS explores connected nodes in an iterative manner, ensuring all vertices are visited at the same level before moving to deeper levels.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Graph Searching Algorithms
Breadth-First Search (BFS) Not discovered u x Discovered, adjacent white nodes Discovered, no adjacent white nodes v y w z
Breadth-First Search (BFS) u x BFS(G, u): 1. Initialize the graph color[u] gray [u] Nil d[u] 0 for each other vertex color[u] white v y w z
Breadth-First Search (BFS) Q u x BFS(G, u): 2. Initialize the queue Q Enqueue(Q, u) v y w z
Breadth-First Search (BFS) t = u Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) v y w z
Breadth-First Search (BFS) t = u r = x, v Q u x BFS(G, u): 3. While Q 2) for each r adj to t if color[r] = white color[r] gray [r] t d[r] d[t] + 1 Enqueue(Q, r) v y w z
Breadth-First Search (BFS) t = u r = x, v Q u x BFS(G, u): 3. While Q 3) color[t] black v y w z
Breadth-First Search (BFS) t = v Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) 2) for each r adj to t 3) color[t] black v y w z
Breadth-First Search (BFS) t = v r = y Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) 2) for each r adj to t 3) color[t] black v y w z
Breadth-First Search (BFS) t = v r = y Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) 2) for each r adj to t 3) color[t] black v y w z
Breadth-First Search (BFS) t = x r = Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) 2) for each r adj to t 3) color[t] black v y w z
Breadth-First Search (BFS) t = y r = w Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) 2) for each r adj to t 3) color[t] black v y w z
Breadth-First Search (BFS) t = w r = z Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) 2) for each r adj to t 3) color[t] black v y w z
Breadth-First Search (BFS) t = z r = Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) 2) for each r adj to t 3) color[t] black v y w z
Breadth-First Search (BFS) u x BFS(G, u): - the shortest-path distance from u v y w z
Breadth-First Search (BFS) u x BFS(G, u): - the shortest-path distance from u - construct a tree v y w z
Breadth-First Search (BFS) u x BFS(G, u): - Initialization: |V| - Enqueuing/dequeuing: |V| - Scanning adj vertices: |E| v y w z
Breadth-First Search (BFS) u x BFS(G, u): - Initialization: O(|V|) - Enqueuing/dequeuing: O(|V|) - Scanning adjacent vertices: O(|E|) => total running time: O(|V| + |E|) v y w z
Depth-First Search (DFS) d[u]: when u is discovered f[u]: when searching adj of u is finished u v w
Depth-First Search (DFS) timestamp: t d[u]: when u is discovered f[u]: when searching adj of u is finished d[u] = t u v w
Depth-First Search (DFS) timestamp: t+1 d[u]: when u is discovered f[u]: when searching adj of u is finished d[u] = t u v w d[v] = t+1
Depth-First Search (DFS) timestamp: t+2 d[u]: when u is discovered f[u]: when searching adj of u is finished d[u] = t u v w d[v] = t+1 f[v] = t+2
Depth-First Search (DFS) timestamp: t+3 d[u]: when u is discovered f[u]: when searching adj of u is finished d[u] = t u v w d[w] = t+3 d[v] = t+1 f[v] = t+2
Depth-First Search (DFS) timestamp: t+4 d[u]: when u is discovered f[u]: when searching adj of u is finished d[u] = t u v w d[w] = t+3 f[v] = t+4 d[v] = t+1 f[v] = t+2
Depth-First Search (DFS) timestamp: t+5 d[u]: when u is discovered f[u]: when searching adj of u is finished d[u] = t f[u] = t+5 u v w d[w] = t+3 f[w] = t+4 d[v] = t+1 f[v] = t+2
Depth-First Search (DFS) d[u]: when u is discovered f[u]: when searching adj of u is finished d[u] = t f[u] = t+5 u 1. d[u] < f[u] 2. [ d[u], f[u] ] entirely contains [ d[v], f[v] ] 3. [ d[v], f[v] ] and [ d[w], f[w] ] are entirely disjoint v w d[w] = t+3 f[w] = t+4 d[v] = t+1 f[v] = t+2
Depth-First Search (DFS) Not discovered u x Discovered, adjacent white nodes Discovered, no adjacent white nodes v y w z
Depth-First Search (DFS) Not discovered u x Discovered, adjacent white nodes Discovered, no adjacent white nodes v y w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization for each u V[G], color[u] white [u] Nil time 0 v y w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting color[u] gray d[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. for each adj v of white [v] u DFS-Visit[v] w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. for each adj v of white [v] u DFS-Visit[v] w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. for each adj v of white [v] u DFS-Visit[v] w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): 1. Initialization 2. For each u V[G] if color[u] = white DFS-Visit(u) v y DFS-Visit(u): 1. Initial Setting 2. Handling adj vertices 3. color[u] black f[u] time time + 1 w z
Depth-First Search (DFS) u x DFS(G): - construct a forest v y w z
Depth-First Search (DFS) u x DFS(G): - Initialization: O(|V|) - Traversing vertices: O(|V|) - Scanning adjacent vertices: O(|E|) => total running time: O(|V| + |E|) v y w z
Topological Sorting Brute-Force way 1. Find a vertex without edges. 2. Put it onto the front of the list, and remove it from G. 3. Remove all edges to the removed edge. 4. Repeat 1~3. m O(|V|2 + |V||E|) Or O(|V|2)
Topological Sorting Using DFS 1. Call DFS(G) 2. When a vertex is finished, put it onto the front of the list. m O(|V| + |E|)
Topological Sorting v enters the list before u? Using DFS 1. Call DFS(G) 2. When a vertex is finished, put it onto the front of the list. 1) v is white: d[u] < d[v] < f[u] 2) v is black: f[v] < d[u] 3) v is gray: d[v] < d[u] < f[v] At d[u]:
