Examples of Graph Traversal: Breadth-First Search (BFS) Example

Discover practical examples of Breadth-First Search (BFS) in graph traversal for real-world applications.
By Jamie

Introduction to Breadth-First Search (BFS)

Breadth-First Search (BFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at a selected node (often called the root) and explores all its neighboring nodes at the present depth prior to moving on to nodes at the next depth level. This method is particularly useful in various applications such as finding the shortest path in unweighted graphs, networking, and more.

Example 1: Social Network Connections

In a social networking application, users can be represented as nodes, and the connections (friendships) between them as edges. BFS can help determine the shortest path to connect two users through mutual friends.

Consider the following graph:

  • Users: A, B, C, D, E, F
  • Connections:
    • A is friends with B and C
    • B is friends with D
    • C is friends with E
    • D is friends with F
    • E is friends with F

Using BFS, starting from User A, we can find the shortest path to User F:

  1. Start at A: [A]
  2. Explore neighbors: [B, C]
  3. Explore B’s neighbors: [D]
  4. Explore C’s neighbors: [E]
  5. Explore D’s neighbors: [F]
  6. Explore E’s neighbors: [F]

The shortest path from A to F is A → B → D → F or A → C → E → F.

Notes:

  • This method ensures that all connections are explored level by level.
  • BFS is ideal in scenarios where the shortest path is needed in unweighted graphs.

Example 2: Finding the Shortest Path in a City Map

In urban navigation applications, cities can be represented as graphs where intersections are nodes and roads are edges. BFS can be utilized to find the shortest route between two locations.

Consider a simplified city map:

  • Intersections: I1, I2, I3, I4, I5
  • Roads:
    • I1 connects to I2 and I3
    • I2 connects to I4
    • I3 connects to I4 and I5
    • I4 connects to I5

If we want to find the shortest path from I1 to I5, we can apply BFS:

  1. Start at I1: [I1]
  2. Explore neighbors: [I2, I3]
  3. Explore I2’s neighbors: [I4]
  4. Explore I3’s neighbors: [I4, I5]
  5. Explore I4’s neighbors: [I5]

The shortest path from I1 to I5 is I1 → I3 → I5.

Notes:

  • BFS is efficient in terms of time complexity, especially for large graphs.
  • The algorithm can handle dynamic graphs where connections might change.

Example 3: Web Crawling for Search Engines

In web crawling, pages can be represented as nodes and hyperlinks as edges. BFS is commonly used by search engines to discover and index new web pages.

Consider a small web structure:

  • Pages: P1, P2, P3, P4, P5
  • Links:
    • P1 links to P2 and P3
    • P2 links to P4
    • P3 links to P4 and P5

When a crawler starts from P1, it uses BFS to explore the web:

  1. Start at P1: [P1]
  2. Explore neighbors: [P2, P3]
  3. Explore P2’s neighbors: [P4]
  4. Explore P3’s neighbors: [P4, P5]

The crawler can now index pages in the order they were discovered, ensuring that it covers all linked pages systematically.

Notes:

  • BFS enables search engines to efficiently index the vast amount of information on the web.
  • The algorithm can help avoid cycles in web crawling by keeping track of visited pages.