DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Algorithm of the Week: Graph Breadth First Search

Algorithm of the Week: Graph Breadth First Search

Stoimen Popov user avatar by
Stoimen Popov
·
Sep. 11, 12 · Interview
Like (1)
Save
Tweet
Share
24.35K Views

Join the DZone community and get the full member experience.

Join For Free

Since we already know how to represent graphs, we can go further for some very simple approaches of walking through them. Passing by all the vertices of a graph is a fundamental technique for most of the graph algorithms, such as finding shortest/longest paths, etc.

First thing to note is that graphs are not trees, in most of the cases, so walking through them can’t start from a root, as we do with trees. What we must do first is to decide from where to start – in other words – choosing a starting vertex.

BFS Choosing a Starting Point

It’s clear that depending on the starting point we can get different passes through the graph. Thus choosing a starting point can be very important for our algorithm!

After that we need to know how to proceed. There are two approaches mostly known as “breadth first” and “depth first” search. While depth first search start from a vertex and goes as far as possible, then walks back and passes through vertices that haven’t been visited yet, breath first search is an approach of passing through all the neighbors of the node first, and then go to the next level.

Overview

We can thing of breadth first search as a “wave” walk through the graph. In other words we go level by level, as shown on the picture below.

BFS Wave

For this very specific graph on the picture we can see how breadth first search walks through the graph level by level!

Initially we mark all vertices as unvisited. A common approach is to create an empty queue where we put the vertices level by level, starting with the initial vertex.

BFS Using a Queue

Using a queue is a typical approach for breadth first search! However this requires more space!

Code

This simple approach is fairly easy to implement. Here’s the PHP implementation in few lines of code.

 

<?php
 
$g = array(
    0 => array(0, 1, 1, 0, 0, 0),
    1 => array(1, 0, 0, 1, 0, 0),
    2 => array(1, 0, 0, 1, 0, 0),
    3 => array(0, 1, 1, 0, 1, 0),
    4 => array(0, 0, 0, 1, 0, 1),
    5 => array(0, 0, 0, 0, 1, 0),
);
 
function init(&$visited, &$graph) 
{
    foreach ($graph as $key => $vertex) {
        $visited[$key] = 0;
    }
}
 
function breadth_first(&$graph, $start, $visited)
{
    // create an empty queue
    $q = array();
 
    // initially enqueue only the starting vertex
    array_push($q, $start);
    $visited[$start] = 1;
    echo $start . "\n";
 
    while (count($q)) {
        $t = array_shift($q);
 
        foreach ($graph[$t] as $key => $vertex) {
            if (!$visited[$key] && $vertex == 1) {
                $visited[$key] = 1;
                array_push($q, $key);
                echo $key . "\t";
            }
        }
        echo "\n";
    }
}
 
$visited = array();
init($visited, $g);
breadth_first($g, 2, $visited);

 

Complexity

The complexity of this algorithm clearly is O(n2).

Application

As I said breadth first and depth first searches are used in many practical cases, as finding shortest/minimal paths etc. That is why understanding these basic principles of walking through a graph is crucial for other, more complex, graph algorithms.

Graph (Unix) Algorithm

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Distributed SQL: An Alternative to Database Sharding
  • Real-Time Stream Processing With Hazelcast and StreamNative
  • What Is a Kubernetes CI/CD Pipeline?
  • The Future of Cloud Engineering Evolves

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: