BFS in Graph
You are given an undirected and disconnected graph G(V, E) having V vertices numbered from 0 to V-1 and E edges. Your task is to print its BFS traversal starting from the 0th vertex.

BFS or Breadth-First Traversal of a graph is an algorithm used to visit all of the nodes of a given graph. In this traversal algorithm, one node is selected, and then all of the adjacent nodes are visited one by one.

An undirected graph is a graph where all the edges are bidirectional, i.e., they point from source to destination and destination to source.

A graph is disconnected if at least two vertices of the graph are not connected by a path.

Note:

1. Here, you need to consider that you need to print the BFS path starting from vertex 0 only. 2. V is the number of vertices present in graph G, and all vertices are numbered from 0 to V-1. 3. E is the number of edges present in graph G. 4. Graph input is provided as the number of vertices and a list of edges. 5. Handle for Disconnected Graphs as well.

For Example: Consider graph:

Here, starting from 0, it is connected to 1 and 2 so, BFS traversal from here will be [0, 1, 2 ]. Now, 3 is also connected to 2. So, BFS traversal becomes [0, 1, 2, 3].

Note:

For each node, the correct order of printing the connected nodes will be sorted order, i.e., if {3,6,9,4} are connected to 1, then the correct order of their printing is {1,3,4,6,9}.

Input Format :

The first line of input contains two integers that denote the value of V and E. Each of the following E lines contains space-separated two integers that denote an edge between vertex A and B.

Output Format :

For each test case, print the BFS Traversal, as described in the task. Output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

0

Question

BFS in Graph

You are given an undirected and disconnected graph G(V, E) having V vertices numbered from 0 to V-1 and E edges. Your task is to print its BFS traversal starting from the 0th vertex.

BFS or Breadth-First Traversal of a graph is an algorithm used to visit all of the nodes of a given graph. In this traversal algorithm, one node is selected, and then all of the adjacent nodes are visited one by one.

An undirected graph is a graph where all the edges are bidirectional, i.e., they point from source to destination and destination to source.

A graph is disconnected if at least two vertices of the graph are not connected by a path.

Note:

1. Here, you need to consider that you need to print the BFS path starting from vertex 0 only. 
2. V is the number of vertices present in graph G, and all vertices are numbered from 0 to V-1. 
3. E is the number of edges present in graph G.
4. Graph input is provided as the number of vertices and a list of edges.
5. Handle for Disconnected Graphs as well.

For Example: Consider graph:

example

Here, starting from 0, it is connected to 1 and 2 so, BFS traversal from here will be [0, 1, 2 ]. Now, 3 is also connected to 2. So, BFS traversal becomes [0, 1, 2, 3].

Note:

For each node, the correct order of printing the connected nodes will be sorted order, i.e., if {3,6,9,4} are connected to 1, then the correct order of their printing is {1,3,4,6,9}.

Input Format :

The first line of input contains two integers that denote the value of V and E.
Each of the following E lines contains space-separated two integers that denote an edge between vertex A and B.

Output Format :

For each test case, print the BFS Traversal, as described in the task.
Output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

0 <= V <= 10^4
0 <= E <= (V * (V - 1)) / 2
0 <= A <= V - 1
0 <= B <= V - 1

Where 'V' is the number of vertices, 'E' is the number of edges, 'A' and 'B' are the vertex numbers.
Time Limit: 1 second

Accepted Answer

BFS is a traversing algorithm we start traversing from a selected node (starting node) and traverse the graph layer wise thus exploring the neighbor nodes (nodes which are directly connected to source node). And then move towards the next-level neighbor nodes.
Pseudocode :
BFS (G, s)
Q.push( s ) //Inserting s in queue Q until all its neighbor vertices are marked.
mark s as visited.
while ( Q is not empty)
//Removing that vertex from queue, whose neighbor will be visited now
u = Q.pop( )
//processing all the neighbors of u
for all neighbors v of u in Graph G
if v is not visited
Q.push( v ) //Stores v in Q to further visit its neighbor
mark w as visited.

Accepted Answer

Using queue

Let us consider a function BFS that accepts a list of edges, EDGES, and the number of vertices VERTEX as a parameter and do:

Create ADJACENCYMATRIX from EDGES.
Define a boolean array VISITED to store nodes that are already visited.
Iterate over VISITED[i] for each 0<= i < VISITED.LENGTH, and check:
1. If VISITED[i] is FALSE, call BFSHELPER function for ADJACENCYMATRIX, i and VISITED.

Now, the function BFSHELPER accepts as parameters, an adjacency matrix of edges ADJACENCYMATRIX, an integer SOURCE and boolean array VISITED and do:

Define a queue, ADJNODE, to store nodes under consideration but not added to the result.
Create an ArrayList RESULT.
Mark VISITED[SOURCE] as TRUE.
Add SOURCE to queue ADJNODE.
Iterate over queue elements until queue ADJNODE is EMPTY:
1. Remove front element from ADJNODE and store it to FRONT
2. Append FRONT to RESULT.
3. Iterate over ADJACENCYMATRIX[FRONT][i] for 0<= i < ADJACENCYMATRIX.LENGTH and check:
  1. If any edge exists between FRONT and i, and i is not VISITED, mark VISITED[i] as TRUE and add i to ADJNODE.
Return RESULT.

Space Complexity: O(n)Explanation:

O(V), where ‘V’ is the number of vertices in the input graph.

Time Complexity: O(n)Explanation:

O(V + E), where ‘V’ is the number of vertices in the input graph, and ‘E’ is the number of edges in the input graph.

C++ (g++ 5.4)

/* 
	Time complexity: O(V + E). 
	Space complexity: O(V^2). 

	Where V is the number of vertices in the input graph and 
    E is the number of edges in the input graph.
*/

#include 

void printBFSHelper(vector> &adjacency_matrix, int source, vector &visited,vector &result)
{
	queue queue;
	visited[source] = true;
	queue.push(source);

	// Traversing all the nodes that are connected to the source node.
	while (!queue.empty())
	{
		int front = queue.front();
		queue.pop();
		result.push_back(front);

		for (int i = 0; i < adjacency_matrix.size(); i++)
		{
			if (adjacency_matrix[front][i] == 1 && !visited[i])
			{
				visited[i] = true;
				queue.push(i);
			}
		}
	}
}

// Converts the given input into adjacency matrix. 
vector> createAdjMat(int vertex, vector> &edges)
{
	vector> adjacency_matrix(vertex);

	for (int i = 0; i < vertex; i++)
	{
		adjacency_matrix[i] = vector(vertex);

		for (int j = 0; j < vertex; j++)
		{
			adjacency_matrix[i][j] = 0;
		}
	}

	for (int i = 0; i < edges.size(); i++)
	{

		adjacency_matrix[edges[i].first][edges[i].second] = 1;
		adjacency_matrix[edges[i].second][edges[i].first] = 1;
	}
	return adjacency_matrix;
}

vector BFS(int vertex, vector> &edges)
{
	vector> adjacency_matrix = createAdjMat(vertex, edges);
	
	vector visited(adjacency_matrix.size());

	for(int i =0; i        visited[i] = false;
    }
	vector result;
	// Traversing through all the nodes.
	for (int i = 0; i < adjacency_matrix.size(); i++)
	{
		if (!visited[i])
		{
			printBFSHelper(adjacency_matrix, i, visited,result);
		}
	}

	return result;

}

Python (3.5)

''' 
	Time complexity: O(V + E). 
	Space complexity: O(V^2). 

	Where V is the number of vertices in the input graph and 
    E is the number of edges in the input graph.
'''

# List for keeping track of the final BFS traversal.
result = [] 

def printBFSHelper(edges, source, visited):

    # A queue for visiting each vertex in the graph.
    queue = []
    # Marking source vertex as already visited.
    visited[source] = True
    queue.append(source)

    # While the queue has vertices to visit keep adding the other vertices 
    # in the queue which are connected by an edge.
    while len(queue) != 0:
        front = queue.pop(0)
        result.append(front)

        for i in range(len(edges)):

            if edges[front][i] == 1 and not visited[i]:
                visited[i] = True
                queue.append(i)

# Function to change the edge matrix representation to 
# adjacency matrix representation of the given graph.
def createAdjMat(vertex, edges):

    adjacency_matrix = [[0] * vertex for _ in range(vertex)]

    for i in range(len(edges[0])):
        adjacency_matrix[edges[0][i]][edges[1][i]] = 1
        adjacency_matrix[edges[1][i]][edges[0][i]] = 1

    return adjacency_matrix


def BFS(vertex, edges):

    # Creating an adjacency matrix representation from the edges given.
    adjacency_matrix = createAdjMat(vertex, edges)
    # Initializing a list for keeping track of already visited vertices.
    visited = [False] * len(adjacency_matrix)

    for i in range(len(visited)):
        
        # Visit the vertex if it is not visited.
        if not visited[i]:
            printBFSHelper(adjacency_matrix, i, visited)

    return result

Java (SE 1.8)

/* 
	Time complexity: O(V + E).
	Space complexity: O(V^2).

	Where V is the number of vertices in the input graph and 
    E is the number of edges in the input graph.
*/

import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;

public class Solution {

	static ArrayList result = new ArrayList<>();

	public static void printBFSHelper(int edges[][], int source, boolean visited[]) {
		
        Queue queue = new LinkedList<>();
		visited[source] = true;
		queue.add(source);

        // Traversing all the nodes that are connected to the source node.
		while (!queue.isEmpty()) {
			int front = queue.remove();
			result.add(front);
			for (int i = 0; i < edges.length; i++) {
				if (edges[front][i] == 1 && !visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}

    // Converts the given input into adjacency matrix. 
	public static int[][] createAdjMat(int vertex, int[][] edges) {
		
        int adjacency_matrix[][] = new int[vertex][vertex];
		
        for (int i = 0; i < edges[0].length; i++) {
			adjacency_matrix[edges[0][i]][edges[1][i]] = 1;
			adjacency_matrix[edges[1][i]][edges[0][i]] = 1;
		}
		
        return adjacency_matrix;
	}

	public static ArrayList BFS(int vertex, int edges[][]) {
		
        int[][] adjacency_matrix = createAdjMat(vertex, edges);
		boolean visited[] = new boolean[adjacency_matrix.length];
		
        // Traversing through all the nodes.
        for (int i = 0; i < visited.length; i++) {
			if (!visited[i]) {
				printBFSHelper(adjacency_matrix, i, visited);
			}
		}
		
        return result;
	}
}

You are given an undirected and disconnected graph G(V, E) having V vertices numbered from 0 to V-1 and E edges. Your task is to print its BFS traversal starting from the 0th vertex.

BFS or Breadth-First Traversal of a graph is an algorithm used to visit all of the nodes of a given graph. In this traversal algorithm, one node is selected, and then all of the adjacent nodes are visited one by one.

An undirected graph is a graph where all the edges are bidirectional, i.e., they point from source to destination and destination to source.

A graph is disconnected if at least two vertices of the graph are not connected by a path.

Note:

For Example: Consider graph:

Note:

Input Format :

Output Format :

Note:

Constraints :

Top PolicyBazaar Software Developer interview questions & answers

Popular interview questions of Software Developer