Breadth First Search (BFS) has been discussed in this article which uses adjacency list for the graph representation. In this article, adjacency matrix will be used to represent the graph.
Adjacency matrix representation: In adjacency matrix representation of a graph, the matrix mat[][] of size n*n (where n is the number of vertices) will represent the edges of the graph where mat[i][j] = 1 represents that there is an edge between the vertices i and j while mat[i][j] = 0 represents that there is no edge between the vertices i and j.
Â
Below is the adjacency matrix representation of the graph shown in the above image:Â
0 1 2 3 0 0 1 1 0 1 1 0 0 1 2 1 0 0 0 3 0 1 0 0
Examples:Â
Input: source = 0
Output: 0 1 2 3 Input: source = 1
Output:1 0 2 3 4
Approach:Â
- Create a matrix of size n*n where every element is 0 representing there is no edge in the graph.
- Now, for every edge of the graph between the vertices i and j set mat[i][j] = 1.
- After the adjacency matrix has been created and filled, find the BFS traversal of the graph as described in this post.
Below is the implementation of the above approach:Â
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;Â
vector<vector<int>> adj;Â
Â
// function to add edge to the graphvoid addEdge(int x,int y){Â Â Â Â adj[x][y] = 1;Â Â Â Â adj[y][x] = 1;}Â
// Function to perform BFS on the graphvoid bfs(int start){    // Visited vector to so that    // a vertex is not visited more than once    // Initializing the vector to false as no    // vertex is visited at the beginning    vector<bool> visited(adj.size(), false);    vector<int> q;    q.push_back(start);      // Set source as visited    visited[start] = true;      int vis;    while (!q.empty()) {        vis = q[0];          // Print the current node        cout << vis << " ";        q.erase(q.begin());          // For every adjacent vertex to the current vertex        for (int i = 0; i < adj[vis].size(); i++) {            if (adj[vis][i] == 1 && (!visited[i])) {                  // Push the adjacent node to the queue                q.push_back(i);                  // Set                visited[i] = true;            }        }    }}  // Driver codeint main(){  // number of vertices  int v = 5;Â
Â
  // adjacency matrix  adj= vector<vector<int>>(v,vector<int>(v,0));Â
  addEdge(0,1);  addEdge(0,2);  addEdge(1,3);     // perform bfs on the graph  bfs(0);} |
Java
// Java implementation of the approachimport java.util.ArrayList;import java.util.Arrays;import java.util.List;Â
class GFG{Â
static class Graph{         // Number of vertex    int v;Â
    // Number of edges    int e;Â
    // Adjacency matrix    int[][] adj;Â
    // Function to fill the empty    // adjacency matrix    Graph(int v, int e)    {        this.v = v;        this.e = e;                 adj = new int[v][v];        for(int row = 0; row < v; row++)            Arrays.fill(adj[row], 0);    }         // Function to add an edge to the graph    void addEdge(int start, int e)     {                 // Considering a bidirectional edge        adj[start][e] = 1;        adj[e][start] = 1;    }Â
    // Function to perform BFS on the graph    void BFS(int start)     {                 // Visited vector to so that        // a vertex is not visited more than once        // Initializing the vector to false as no        // vertex is visited at the beginning        boolean[] visited = new boolean[v];        Arrays.fill(visited, false);        List<Integer> q = new ArrayList<>();        q.add(start);Â
        // Set source as visited        visited[start] = true;Â
        int vis;        while (!q.isEmpty())        {            vis = q.get(0);Â
            // Print the current node            System.out.print(vis + " ");            q.remove(q.get(0));Â
            // For every adjacent vertex to            // the current vertex            for(int i = 0; i < v; i++)            {                if (adj[vis][i] == 1 && (!visited[i]))                {                                         // Push the adjacent node to                    // the queue                    q.add(i);Â
                    // Set                    visited[i] = true;                }            }        }    }}Â
// Driver codepublic static void main(String[] args){Â Â Â Â Â Â Â Â Â int v = 5, e = 4;Â
    // Create the graph    Graph G = new Graph(v, e);    G.addEdge(0, 1);    G.addEdge(0, 2);    G.addEdge(1, 3);Â
    G.BFS(0);}}Â
// This code is contributed by sanjeev2552 |
Python3
# Python3 implementation of the approach class Graph:Â Â Â Â Â Â Â Â Â adj = []Â
    # Function to fill empty adjacency matrix    def __init__(self, v, e):                 self.v = v        self.e = e        Graph.adj = [[0 for i in range(v)]                         for j in range(v)]Â
    # Function to add an edge to the graph    def addEdge(self, start, e):                 # Considering a bidirectional edge        Graph.adj[start][e] = 1        Graph.adj[e][start] = 1Â
    # Function to perform DFS on the graph    def BFS(self, start):                 # Visited vector to so that a        # vertex is not visited more than         # once Initializing the vector to         # false as no vertex is visited at        # the beginning         visited = [False] * self.v        q = [start]Â
        # Set source as visited        visited[start] = TrueÂ
        while q:            vis = q[0]Â
            # Print current node            print(vis, end = ' ')            q.pop(0)                         # For every adjacent vertex to             # the current vertex            for i in range(self.v):                if (Graph.adj[vis][i] == 1 and                      (not visited[i])):                                               # Push the adjacent node                     # in the queue                    q.append(i)                                         # set                    visited[i] = TrueÂ
# Driver codev, e = 5, 4Â
# Create the graphG = Graph(v, e)G.addEdge(0, 1)G.addEdge(0, 2)G.addEdge(1, 3)Â
# Perform BFSG.BFS(0)Â
# This code is contributed by ng24_7 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;Â
public class GFG{Â
  class Graph  {Â
    // Number of vertex    public int v;Â
    // Number of edges    public int e;Â
    // Adjacency matrix    public int[,] adj;Â
    // Function to fill the empty    // adjacency matrix    public Graph(int v, int e)    {      this.v = v;      this.e = e;Â
      adj = new int[v,v];      for(int row = 0; row < v; row++)        for(int col = 0; col < v; col++)          adj[row, col] = 0;    }Â
    // Function to add an edge to the graph    public void addEdge(int start, int e)     {Â
      // Considering a bidirectional edge      adj[start, e] = 1;      adj[e, start] = 1;    }Â
    // Function to perform BFS on the graph    public void BFS(int start)     {Â
      // Visited vector to so that      // a vertex is not visited more than once      // Initializing the vector to false as no      // vertex is visited at the beginning      bool[] visited = new bool[v];      List<int> q = new List<int>();      q.Add(start);Â
      // Set source as visited      visited[start] = true;Â
      int vis;      while (q.Count != 0)      {        vis = q[0];Â
        // Print the current node        Console.Write(vis + " ");        q.Remove(q[0]);Â
        // For every adjacent vertex to        // the current vertex        for(int i = 0; i < v; i++)        {          if (adj[vis,i] == 1 && (!visited[i]))          {Â
            // Push the adjacent node to            // the queue            q.Add(i);Â
            // Set            visited[i] = true;          }        }      }    }  }Â
  // Driver code  public static void Main(String[] args)  {Â
    int v = 5, e = 4;Â
    // Create the graph    Graph G = new Graph(v, e);    G.addEdge(0, 1);    G.addEdge(0, 2);    G.addEdge(1, 3);Â
    G.BFS(0);  }}Â
// This code is contributed by shikhasingrajput |
Javascript
// JavaScript implementation of the approachconst adj = [];Â
// function to add edge to the graphfunction addEdge(x, y) {Â Â adj[x][y] = 1;Â Â adj[y][x] = 1;}Â
// Function to perform BFS on the graphfunction bfs(start) {  // Visited array to keep track of visited nodes  // Initializing the array with all false values as no vertex  // is visited at the beginning  const visited = Array(adj.length).fill(false);  const q = [];  q.push(start);Â
  // Set source as visited  visited[start] = true;Â
  let vis;  while (q.length >0) {    vis = q.shift();Â
    // Print the current node    console.log(vis + " ");Â
    // For every adjacent vertex to the current vertex    for (let i = 0; i < adj[vis].length; i++) {      if (adj[vis][i] === 1 && !visited[i]) {        // Push the adjacent node to the queue        q.push(i);Â
        // Set the adjacent node as visited        visited[i] = true;      }    }  }}Â
// Driver codeÂ
  // number of vertices  const v = 5;Â
  // adjacency matrix  for (let i = 0; i < v; i++) {    adj[i] = Array(v).fill(0);  }Â
  addEdge(0, 1);  addEdge(0, 2);  addEdge(1, 3);Â
  // perform bfs on the graph  bfs(0); |
Output:Â
0 1 2 3
Â
Time Complexity: O(N*N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
