Understanding Breadth-First Search (BFS) Algorithm for Graph Searching

Slide Note
Embed
Share

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.


Uploaded on Jul 10, 2024 | 1 Views


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


  1. Graph Searching Algorithms

  2. Tree

  3. Breadth-First Search (BFS)

  4. Breadth-First Search (BFS) Not discovered u x Discovered, adjacent white nodes Discovered, no adjacent white nodes v y w z

  5. 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

  6. Breadth-First Search (BFS) Q u x BFS(G, u): 2. Initialize the queue Q Enqueue(Q, u) v y w z

  7. Breadth-First Search (BFS) t = u Q u x BFS(G, u): 3. While Q 1) t Dequeue(Q) v y w z

  8. 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

  9. 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

  10. 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

  11. 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

  12. 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

  13. 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

  14. 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

  15. 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

  16. 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

  17. Breadth-First Search (BFS) u x BFS(G, u): - the shortest-path distance from u v y w z

  18. Breadth-First Search (BFS) u x BFS(G, u): - the shortest-path distance from u - construct a tree v y w z

  19. Breadth-First Search (BFS) u x BFS(G, u): - Initialization: |V| - Enqueuing/dequeuing: |V| - Scanning adj vertices: |E| v y w z

  20. 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

  21. Depth-First Search (DFS)

  22. Depth-First Search (DFS) d[u]: when u is discovered f[u]: when searching adj of u is finished u v w

  23. 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

  24. 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

  25. 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

  26. 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

  27. 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

  28. 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

  29. 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

  30. Depth-First Search (DFS) Not discovered u x Discovered, adjacent white nodes Discovered, no adjacent white nodes v y w z

  31. Depth-First Search (DFS) Not discovered u x Discovered, adjacent white nodes Discovered, no adjacent white nodes v y w z

  32. 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

  33. 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

  34. 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

  35. 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

  36. 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

  37. 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

  38. 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

  39. 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

  40. 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

  41. 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

  42. 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

  43. 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

  44. 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

  45. Depth-First Search (DFS) u x DFS(G): - construct a forest v y w z

  46. 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

  47. Topological Sorting

  48. 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)

  49. 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|)

  50. 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]:

Related


More Related Content