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!
