CO2412 Computational Thinking Lecture 11

CO2412: Computational Thinking
Lecture 11

Introduction to Graph Traversal
1. Graph Traversal Basics
o Graph traversal refers to the process of visiting, checking, and
updating each vertex in a graph.
o Two primary methods of traversal are:

 Breadth-First Search (BFS)
 Depth-First Search (DFS)
2. Importance of Graph Traversal
o Graph traversal is critical in solving many computational problems
such as searching for a path, exploring all possible configurations,
and more.


Breadth-First Search (BFS)
1. What is BFS?
o BFS is a graph traversal method that explores all vertices at the
present depth level before moving on to vertices at the next depth
level.
o BFS uses a queue data structure to keep track of vertices to be
explored.
2. BFS Algorithm
o Step-by-Step Process:

1. Start at the root (or any arbitrary node) and mark it as
visited.
2. Add the starting node to a queue.
3. While the queue is not empty:
 Dequeue a node and explore its neighbors.
 If a neighbor has not been visited, mark it as visited
and enqueue it.
4. Repeat until all nodes at the current depth level have been
explored.