Execute BFS in disconnected graph
Traversing a graph is a fundamental operation in computer science, allowing us to explore relationships between various elements. In a disconnected graph, there are multiple disconnected components or subgraphs that are not connected by edges. The Breadth First Traversal (BFS) algorithm can be employed to systematically explore such disconnected graphs. This article demonstrates how to execute BFS in a disconnected graph and provides an in-depth explanation of the process.
Problem Statement and Description
Given a disconnected graph represented using an adjacency list, the task is to perform Breadth First Traversal starting from a specific vertex. A disconnected graph consists of multiple subgraphs, where each subgraph might not be directly connected to the others. The BFS algorithm systematically explores all connected vertices within each subgraph while considering the disconnected nature of the graph.
Example
Consider a disconnected graph with 7 vertices and the following edges:
0 -> 1, 5
1 -> (no edges)
2 -> 1, 6
3 -> 2, 4
4 -> 5
5 -> (no edges)
6 -> 0, 5
If we start BFS from vertex 6, the traversal sequence will be: 6 0 5 1 2 3 4.
Idea to Solve the Problem
To perform BFS in a disconnected graph, we need to ensure that all the connected components are visited. We achieve this by iterating through all the vertices and executing BFS from each unvisited vertex. By doing this, we explore every connected component, ensuring that no vertex is left unvisited.
Pseudocode
Here's the pseudocode for executing BFS in a disconnected graph:
procedure BFS_Disconnected(graph):
for each vertex in graph:
if vertex is not visited:
BFS(vertex)
procedure BFS(start):
queue.enqueue(start)
mark start as visited
while queue is not empty:
vertex = queue.dequeue()
process(vertex)
for each adjacent_vertex of vertex:
if adjacent_vertex is not visited:
queue.enqueue(adjacent_vertex)
mark adjacent_vertex as visited
Algorithm Explanation
- For each vertex in the graph: a. If the vertex has not been visited, execute BFS from that vertex.
- The BFS algorithm remains the same as in a connected graph (explained in the previous response).
- This nested approach ensures that we visit all vertices within each connected component.
Code Solution
//C Program
//Perform bfs in disconnected graph
#include<stdio.h>
#include<stdlib.h>
struct AjlistNode {
int vId; //Vertices id
struct AjlistNode *next;
};
struct Graph {
int data; //node key value
struct AjlistNode *next;
};
struct Queue {
int element;
struct Queue *next;
};
int size; //number of nodes
//set node key value
void set_data(struct Graph *node) {
if (node != NULL && size > 0) {
int index = 0;
for (index; index < size; index++) {
//set vertic node data
node[index].data = index; //set node key
//Initial no AjlistNode
//Set NULL Value
node[index].next = NULL;
}
} else {
printf("Vertic Node is Empty");
}
}
//Add Queue Element
void enqueue(int data, struct Queue **queue) {
struct Queue *newNode = (struct Queue *) malloc(sizeof(struct Queue));
if (newNode != NULL) {
newNode->element = data;
newNode->next = NULL;
if ( *queue != NULL) {
struct Queue *temp = *queue;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
} else {
*queue = newNode;
}
} else {
printf("\n Memory overflow");
}
}
//remove single element into queue
void dequeue(struct Queue **queue) {
struct Queue *temp = ( *queue);
( *queue) = temp->next;
free(temp);
temp = NULL;
}
//Add Edge from Two given Nodes
void add_edge(struct Graph *node, int V, int E) {
//add edge form V to E
//V and E is Node location
if (V < size && E < size) {
//first create Adjacency node
struct AjlistNode *newEdge = (struct AjlistNode *) malloc(
sizeof(struct AjlistNode)
);
if (newEdge != NULL) {
newEdge->next = NULL;
newEdge->vId = E;
struct AjlistNode *temp = node[V].next;
if (temp == NULL) {
node[V].next = newEdge;
} else {
//Add node at last
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newEdge;
}
} else {
printf("\n Memory overflow");
}
} else {
//not valid Vertices
printf("Invalid Node Vertices %d %d", V, E);
}
}
//Display Adjacency list of vertex
void print_graph(struct Graph *node) {
if (node != NULL) {
struct AjlistNode *temp = NULL;
for (int index = 0; index < size; index++) {
printf("\n Adjacency list of vertex %d :", index);
temp = node[index].next;
while (temp != NULL) {
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data
printf(" %d", node[temp->vId].data);
temp = temp->next;
}
}
} else {
printf("Empty Graph");
}
}
//Breadth First Traversal for a directed graph node
void bfs(int point, struct Graph *node, int *visit) {
struct Queue *queue = NULL;
struct AjlistNode *temp = NULL;
//Add first element into queue
enqueue(point, & queue);
while (queue != NULL) {
temp = node[queue->element].next;
while (temp != NULL) {
if (visit[temp->vId] == 0) {
visit[temp->vId] = 1;
enqueue(temp->vId, & queue);
}
temp = temp->next;
}
visit[queue->element] = 1;
printf("%3d", queue->element);
dequeue( & queue);
}
}
void view_bfs(int point, struct Graph *node) {
if (point > size || node == NULL) {
return;
}
printf("\n bfs :");
int *visit = (int *) calloc(size, sizeof(int));
bfs(point, node, visit);
for (int i = 0; i < size; ++i) {
if (visit[i] == 0) {
bfs(i, node, visit);
}
}
}
int main() {
//Set number of graph node
size = 7;
struct Graph *node = NULL;
node = (struct Graph *) malloc(sizeof(struct Graph) *size);
if (node == NULL) {
printf("\n Memory overflow");
} else {
//First set node keys
set_data(node);
//Connected two node with Edges
add_edge(node, 0, 1);
add_edge(node, 0, 5);
add_edge(node, 2, 1);
add_edge(node, 2, 6);
add_edge(node, 3, 2);
add_edge(node, 3, 4);
add_edge(node, 4, 5);
add_edge(node, 6, 0);
add_edge(node, 6, 5);
print_graph(node);
int start = 6;
view_bfs(start, node);
}
return 0;
}
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs : 6 0 5 1 2 3 4
// C++ program
// Perform bfs in disconnected graph
#include<iostream>
using namespace std;
class AjlistNode {
public:
//Vertices node key
int id;
AjlistNode *next;
AjlistNode(int value) {
//Set value of node key
this->id = value;
this->next = NULL;
}
};
class Vertices {
public:
int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int value) {
this->data = value;
this->next = NULL;
}
};
class MyQueue {
public:
int element;
MyQueue *next;
MyQueue(int value) {
this->element = value;
this->next = NULL;
}
};
class MyGraph {
public:
//number of Vertices
int size;
Vertices *node;
MyQueue *front;
MyQueue *tail;
MyGraph(int value) {
//set value
this->front = NULL;
this->tail = NULL;
this->size = value;
this->node = new Vertices[size];
//set initial values of graph node
this->set_data();
}
//Set initial node value
void set_data() {
if (this->node == NULL) {
cout << "\nEmpty Graph";
} else {
int index = 0;
while (index < this->size) {
this->node[index] = index;
index++;
}
}
}
//Connect two node
void add_edge(int start, int end) {
AjlistNode *newEdge = new AjlistNode(end);
if (this->node[start].next == NULL) {
//Include first adjacency list node of location start
this->node[start].next = newEdge;
} else {
AjlistNode *temp = this->node[start].next;
//Add new node at the end of edge
while (temp->next != NULL) {
temp = temp->next;
}
//Add node
temp->next = newEdge;
}
}
//Display graph elements
void print_graph() {
if (this->size > 0 &&
this->node != NULL) {
int index = 0;
while (index < this->size) {
cout << "\nAdjacency list of vertex " << index << " :";
AjlistNode *temp = this->node[index].next;
while (temp != NULL) {
cout << this->node[temp->id].data << " ";
temp = temp->next;
}
index++;
}
}
}
void enqueue(int value) {
MyQueue *newNode = new MyQueue(value);
if (newNode != NULL) {
if (this->front == NULL) {
this->front = newNode;
this->tail = newNode;
} else {
this->tail->next = newNode;
this->tail = newNode;
}
} else {
cout << "\n Memory overflow";
}
}
void dequeue() {
MyQueue *temp = this->front;
this->front = temp->next;
if (this->tail == temp) {
this->tail = NULL;
}
temp = NULL;
}
void bfs(int point, bool visit[]) {
AjlistNode *temp = NULL;
this->enqueue(point);
while (this->front != NULL) {
temp = this->node[this->front->element].next;
while (temp != NULL) {
if (visit[temp->id] == false) {
visit[temp->id] = true;
this->enqueue(temp->id);
}
temp = temp->next;
}
visit[this->front->element] = true;
cout << this->front->element << " ";
this->dequeue();
}
}
void view_bfs(int point) {
if (point > this->size ||
this->node == NULL) {
return;
}
bool *visit = new bool[size];
int i = 0;
cout << "\n bfs : ";
this->bfs(point, visit);
while (i < this->size) {
if (visit[i] == false) {
this->bfs(i, visit);
}
i++;
}
}
};
int main() {
//Number of nodes
int totalNode = 7;
MyGraph g = MyGraph(totalNode);
//Connected two node with Edges
g.add_edge(0, 1);
g.add_edge(0, 5);
g.add_edge(2, 1);
g.add_edge(2, 6);
g.add_edge(3, 2);
g.add_edge(3, 4);
g.add_edge(4, 5);
g.add_edge(6, 0);
g.add_edge(6, 5);
g.print_graph();
//Start location
int start = 6;
g.view_bfs(start);
return 0;
}
Output
Adjacency list of vertex 0 :1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 :1 6
Adjacency list of vertex 3 :2 4
Adjacency list of vertex 4 :5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 :0 5
bfs : 6 0 5 1 2 3 4
// Java program
// Perform bfs in disconnected graph
class AjlistNode {
//Vertices node key
public int id;
public AjlistNode next;
public AjlistNode(int value) {
//Set value of node key
id = value;
next = null;
}
}
class Vertices {
public int data;
public AjlistNode next;
public Vertices(int value) {
data = value;
next = null;
}
}
class MyQueue {
public int element;
public MyQueue next;
public MyQueue(int value)
{
element = value;
next = null;
}
}
public class MyGraph {
//number of Vertices
private int size;
private Vertices[] node;
private MyQueue front;
private MyQueue tail;
public MyGraph(int value) {
//set value
front = null;
tail = null;
size = value;
node = new Vertices[size];
//set initial values of graph node
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
System.out.println("\nEmpty Graph");
} else {
int index = 0;
while (index < size) {
node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
public void add_edge(int start, int end) {
AjlistNode newEdge = new AjlistNode(end);
if (node[start].next == null)
{
//Include first adjacency list node of location start
node[start].next = newEdge;
}
else
{
AjlistNode temp = node[start].next;
//Add new node at the end of edge
while (temp.next != null)
{
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {
if (size > 0 && node != null) {
int index = 0;
while (index < size) {
System.out.print("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = node[index].next;
while (temp != null) {
System.out.print(node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
public void enqueue(int value) {
MyQueue newNode = new MyQueue(value);
if (newNode != null) {
if (front == null) {
front = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
} else {
System.out.print("\n Memory overflow");
}
}
public void dequeue() {
MyQueue temp = front;
front = temp.next;
if (tail == temp) {
tail = null;
}
temp = null;
}
public void bfs(int point, boolean[] visit) {
AjlistNode temp = null;
enqueue(point);
while (front != null) {
temp = node[front.element].next;
while (temp != null) {
if (visit[temp.id] == false) {
visit[temp.id] = true;
enqueue(temp.id);
}
temp = temp.next;
}
visit[front.element] = true;
System.out.print(front.element + " ");
dequeue();
}
}
public void view_bfs(int point) {
if (point > size || node == null) {
return;
}
boolean[] visit = new boolean[size];
int i = 0;
System.out.print("\n bfs : ");
bfs(point, visit);
while (i < size) {
if (visit[i] == false) {
bfs(i, visit);
}
i++;
}
}
public static void main(String[] args) {
//Number of nodes
int totalNode = 7;
MyGraph g = new MyGraph(totalNode);
//Connected two node with Edges
g.add_edge(0, 1);
g.add_edge(0, 5);
g.add_edge(2, 1);
g.add_edge(2, 6);
g.add_edge(3, 2);
g.add_edge(3, 4);
g.add_edge(4, 5);
g.add_edge(6, 0);
g.add_edge(6, 5);
g.print_graph();
//Start location
int start = 6;
g.view_bfs(start);
}
}
Output
Adjacency list of vertex 0 :1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 :1 6
Adjacency list of vertex 3 :2 4
Adjacency list of vertex 4 :5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 :0 5
bfs : 6 0 5 1 2 3 4
// C# program
// Perform bfs in disconnected graph
using System;
class AjlistNode {
//Vertices node key
public int id;
public AjlistNode next;
public AjlistNode(int value) {
//Set value of node key
id = value;
next = null;
}
}
class Vertices {
public int data;
public AjlistNode next;
public Vertices(int value) {
data = value;
next = null;
}
}
class MyQueue {
public int element;
public MyQueue next;
public MyQueue(int value) {
element = value;
next = null;
}
}
public class MyGraph {
//number of Vertices
private int size;
private Vertices[] node;
private MyQueue front;
private MyQueue tail;
public MyGraph(int value) {
//set value
front = null;
tail = null;
size = value;
node = new Vertices[size];
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
Console.WriteLine("\nEmpty Graph");
} else {
int index = 0;
while (index < size) {
node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
public void add_edge(int start, int end) {
AjlistNode newEdge = new AjlistNode(end);
if (node[start].next == null) {
//Include first adjacency list node of location start
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;
//Add new node at the end of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
public void print_graph() {
if (size > 0 &&
node != null) {
int index = 0;
while (index < size) {
Console.Write("\nAdjacency list of vertex " + index + " : ");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
public void enqueue(int value) {
MyQueue newNode = new MyQueue(value);
if (newNode != null) {
if (front == null) {
front = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
} else {
Console.Write("\n Memory overflow");
}
}
public void dequeue() {
MyQueue temp = front;
front = temp.next;
if (tail == temp) {
tail = null;
}
temp = null;
}
public void bfs(int point, Boolean[] visit) {
AjlistNode temp = null;
enqueue(point);
while (front != null) {
temp = node[front.element].next;
while (temp != null) {
if (visit[temp.id] == false) {
visit[temp.id] = true;
enqueue(temp.id);
}
temp = temp.next;
}
visit[front.element] = true;
Console.Write(front.element + " ");
dequeue();
}
}
public void view_bfs(int point) {
if (point > size ||
node == null) {
return;
}
Boolean[] visit = new Boolean[size];
int i = 0;
Console.Write("\n bfs : ");
bfs(point, visit);
while (i < size) {
if (visit[i] == false) {
bfs(i, visit);
}
i++;
}
}
public static void Main(String[] args) {
//Number of nodes
int totalNode = 7;
MyGraph g = new MyGraph(totalNode);
g.add_edge(0, 1);
g.add_edge(0, 5);
g.add_edge(2, 1);
g.add_edge(2, 6);
g.add_edge(3, 2);
g.add_edge(3, 4);
g.add_edge(4, 5);
g.add_edge(6, 0);
g.add_edge(6, 5);
g.print_graph();
//Start location
int start = 6;
g.view_bfs(start);
}
}
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs : 6 0 5 1 2 3 4
<?php
// Php program
// Perform bfs in disconnected graph
class AjlistNode {
//Vertices node key
public $id;
public $next;
function __construct($value) {
//Set value of node key
$this->id = $value;
$this->next = null;
}
}
class Vertices {
public $data;
public $next;
function __construct($value) {
$this->data = $value;
$this->next = null;
}
}
class MyQueue {
public $element;
public $next;
function __construct($value) {
$this->element = $value;
$this->next = null;
}
}
class MyGraph {
//number of Vertices
private $size;
private $node;
private $front;
private $tail;
function __construct($value) {
//set value
$this->front = null;
$this->tail = null;
$this->size = $value;
$this->node = array_fill(0, $this->size, null);
//set initial values of graph node
$this->set_data();
}
//Set initial node value
public function set_data() {
if ($this->node == null) {
echo("\nEmpty Graph");
} else {
$index = 0;
while ($index < $this->size) {
$this->node[$index] = new Vertices($index);
$index++;
}
}
}
//Connect two node
public function add_edge($start, $last) {
$newEdge = new AjlistNode($last);
if ($this->node[$start]->next == null) {
//Include first adjacency list node of location start
$this->node[$start]->next = $newEdge;
} else {
$temp = $this->node[$start]->next;
//Add new node at the end of edge
while ($temp->next != null) {
$temp = $temp->next;
}
//Add node
$temp->next = $newEdge;
}
}
//Display graph elements
public function print_graph() {
if ($this->size > 0 &&
$this->node != null) {
$index = 0;
while ($index < $this->size) {
echo("\nAdjacency list of vertex ". $index ." : ");
$temp = $this->node[$index]->next;
while ($temp != null) {
echo($this->node[$temp->id]->data ." ");
$temp = $temp->next;
}
$index++;
}
}
}
public function enqueue($value) {
$newNode = new MyQueue($value);
if ($newNode != null) {
if ($this->front == null) {
$this->front = $newNode;
$this->tail = $newNode;
} else {
$this->tail->next = $newNode;
$this->tail = $newNode;
}
} else {
echo("\n Memory overflow");
}
}
public function dequeue() {
$temp = $this->front;
$this->front = $temp->next;
if ($this->tail == $temp) {
$this->tail = null;
}
$temp = null;
}
public function bfs($point, & $visit) {
$temp = null;
$this->enqueue($point);
while ($this->front != null) {
$temp = $this->node[$this->front->element]->next;
while ($temp != null) {
if ($visit[$temp->id] == false) {
$visit[$temp->id] = true;
$this->enqueue($temp->id);
}
$temp = $temp->next;
}
$visit[$this->front->element] = true;
echo($this->front->element ." ");
$this->dequeue();
}
}
public function view_bfs($point) {
if ($point > $this->size ||
$this->node == null) {
return;
}
$visit = array_fill(0, $this->size, false);
$i = 0;
echo("\n bfs : ");
$this->bfs($point, $visit);
while ($i < $this->size) {
if ($visit[$i] == false) {
$this->bfs($i, $visit);
}
$i++;
}
}
}
function main() {
//Number of nodes
$totalNode = 7;
$g = new MyGraph($totalNode);
//Connected two node with Edges
$g->add_edge(0, 1);
$g->add_edge(0, 5);
$g->add_edge(2, 1);
$g->add_edge(2, 6);
$g->add_edge(3, 2);
$g->add_edge(3, 4);
$g->add_edge(4, 5);
$g->add_edge(6, 0);
$g->add_edge(6, 5);
$g->print_graph();
//Start location
$start = 6;
$g->view_bfs($start);
}
main();
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs : 6 0 5 1 2 3 4
// Node Js program
// Perform bfs in disconnected graph
class AjlistNode {
//Vertices node key
constructor(value) {
//Set value of node key
this.id = value;
this.next = null;
}
}
class Vertices {
constructor(value) {
this.data = value;
this.next = null;
}
}
class MyQueue {
constructor(value) {
this.element = value;
this.next = null;
}
}
class MyGraph {
//number of Vertices
constructor(value) {
//set value
this.front = null;
this.tail = null;
this.size = value;
this.node = Array(this.size).fill(null);
//set initial values of graph node
this.set_data();
}
//Set initial node value
set_data() {
if (this.node == null) {
process.stdout.write("\nEmpty Graph");
} else {
var index = 0;
while (index < this.size) {
this.node[index] = new Vertices(index);
index++;
}
}
}
//Connect two node
add_edge(start, last) {
var newEdge = new AjlistNode(last);
if (this.node[start].next == null) {
//Include first adjacency list node of location start
this.node[start].next = newEdge;
} else {
var temp = this.node[start].next;
//Add new node at the end of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
print_graph() {
if (this.size > 0 &&
this.node != null) {
var index = 0;
while (index < this.size) {
process.stdout.write("\nAdjacency list of vertex " + index + " : ");
var temp = this.node[index].next;
while (temp != null) {
process.stdout.write(this.node[temp.id].data + " ");
temp = temp.next;
}
index++;
}
}
}
enqueue(value) {
var newNode = new MyQueue(value);
if (newNode != null) {
if (this.front == null) {
this.front = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
} else {
process.stdout.write("\n Memory overflow");
}
}
dequeue() {
var temp = this.front;
this.front = temp.next;
if (this.tail == temp) {
this.tail = null;
}
temp = null;
}
bfs(point, visit) {
var temp = null;
this.enqueue(point);
while (this.front != null) {
temp = this.node[this.front.element].next;
while (temp != null) {
if (visit[temp.id] == false) {
visit[temp.id] = true;
this.enqueue(temp.id);
}
temp = temp.next;
}
visit[this.front.element] = true;
process.stdout.write(this.front.element + " ");
this.dequeue();
}
}
view_bfs(point) {
if (point > this.size ||
this.node == null) {
return;
}
var visit = Array(this.size).fill(false);
var i = 0;
process.stdout.write("\n bfs : ");
this.bfs(point, visit);
while (i < this.size) {
if (visit[i] == false) {
this.bfs(i, visit);
}
i++;
}
}
}
function main(args) {
//Number of nodes
var totalNode = 7;
var g = new MyGraph(totalNode);
//Connected two node with Edges
g.add_edge(0, 1);
g.add_edge(0, 5);
g.add_edge(2, 1);
g.add_edge(2, 6);
g.add_edge(3, 2);
g.add_edge(3, 4);
g.add_edge(4, 5);
g.add_edge(6, 0);
g.add_edge(6, 5);
g.print_graph();
//Start location
var start = 6;
g.view_bfs(start);
}
main();
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs : 6 0 5 1 2 3 4
# Python 3 program
# Perform bfs in disconnected graph
class AjlistNode :
def __init__(self, value) :
# Set value of node key
self.id = value
self.next = None
class Vertices :
def __init__(self, value) :
self.data = value
self.next = None
class MyQueue :
def __init__(self, value) :
self.element = value
self.next = None
class MyGraph :
def __init__(self, value) :
# set value
self.front = None
self.tail = None
self.size = value
self.node = [None] * self.size
# set initial values of graph node
self.set_data()
# Set initial node value
def set_data(self) :
if (self.node == None) :
print("\nEmpty Graph", end = "")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1
# Connect two node
def add_edge(self, start, last) :
newEdge = AjlistNode(last)
if (self.node[start].next == None) :
# Include first adjacency list node of location start
self.node[start].next = newEdge
else :
temp = self.node[start].next
# Add new node at the end of edge
while (temp.next != None) :
temp = temp.next
# Add node
temp.next = newEdge
# Display graph elements
def print_graph(self) :
if (self.size > 0 and self.node != None) :
index = 0
while (index < self.size) :
print("\nAdjacency list of vertex ", index ," : ", end = "")
temp = self.node[index].next
while (temp != None) :
print(self.node[temp.id].data ," ", end = "")
temp = temp.next
index += 1
def enqueue(self, value) :
newNode = MyQueue(value)
if (newNode != None) :
if (self.front == None) :
self.front = newNode
self.tail = newNode
else :
self.tail.next = newNode
self.tail = newNode
else :
print("\n Memory overflow", end = "")
def dequeue(self) :
temp = self.front
self.front = temp.next
if (self.tail == temp) :
self.tail = None
temp = None
def bfs(self, point, visit) :
temp = None
self.enqueue(point)
while (self.front != None) :
temp = self.node[self.front.element].next
while (temp != None) :
if (visit[temp.id] == False) :
visit[temp.id] = True
self.enqueue(temp.id)
temp = temp.next
visit[self.front.element] = True
print(self.front.element ," ", end = "")
self.dequeue()
def view_bfs(self, point) :
if (point > self.size or self.node == None) :
return
visit = [False] * self.size
i = 0
print("\n bfs : ", end = "")
self.bfs(point, visit)
while (i < self.size) :
if (visit[i] == False) :
self.bfs(i, visit)
i += 1
def main() :
# Number of nodes
totalNode = 7
g = MyGraph(totalNode)
# Connected two node with Edges
g.add_edge(0, 1)
g.add_edge(0, 5)
g.add_edge(2, 1)
g.add_edge(2, 6)
g.add_edge(3, 2)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.add_edge(6, 0)
g.add_edge(6, 5)
g.print_graph()
# Start location
start = 6
g.view_bfs(start)
if __name__ == "__main__":
main()
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs : 6 0 5 1 2 3 4
# Ruby program
# Perform bfs in disconnected graph
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_reader :id, :next
attr_accessor :id, :next
def initialize(value)
# Set value of node key
@id = value
@next = nil
end
end
class Vertices
# Define the accessor and reader of class Vertices
attr_reader :data, :next
attr_accessor :data, :next
def initialize(value)
@data = value
@next = nil
end
end
class MyQueue
# Define the accessor and reader of class MyQueue
attr_reader :element, :next
attr_accessor :element, :next
def initialize(value)
@element = value
@next = nil
end
end
class MyGraph
# Define the accessor and reader of class MyGraph
attr_reader :size, :node, :front, :tail
attr_accessor :size, :node, :front, :tail
def initialize(value)
# set value
@front = nil
@tail = nil
@size = value
@node = Array.new(@size) {nil}
# set initial values of graph node
self.set_data()
end
# Set initial node value
def set_data()
if (@node == nil)
print("\nEmpty Graph")
else
index = 0
while (index < @size)
@node[index] = Vertices.new(index)
index += 1
end
end
end
# Connect two node
def add_edge(start, last)
newEdge = AjlistNode.new(last)
if (@node[start].next == nil)
# Include first adjacency list node of location start
@node[start].next = newEdge
else
temp = @node[start].next
# Add new node at the end of edge
while (temp.next != nil)
temp = temp.next
end
# Add node
temp.next = newEdge
end
end
# Display graph elements
def print_graph()
if (@size > 0 &&
@node != nil)
index = 0
while (index < @size)
print("\nAdjacency list of vertex ", index ," : ")
temp = @node[index].next
while (temp != nil)
print(@node[temp.id].data ," ")
temp = temp.next
end
index += 1
end
end
end
def enqueue(value)
newNode = MyQueue.new(value)
if (newNode != nil)
if (@front == nil)
@front = newNode
@tail = newNode
else
@tail.next = newNode
@tail = newNode
end
else
print("\n Memory overflow")
end
end
def dequeue()
temp = @front
@front = temp.next
if (@tail == temp)
@tail = nil
end
temp = nil
end
def bfs(point, visit)
temp = nil
self.enqueue(point)
while (@front != nil)
temp = @node[@front.element].next
while (temp != nil)
if (visit[temp.id] == false)
visit[temp.id] = true
self.enqueue(temp.id)
end
temp = temp.next
end
visit[@front.element] = true
print(@front.element ," ")
self.dequeue()
end
end
def view_bfs(point)
if (point > @size ||
@node == nil)
return
end
visit = Array.new(@size) {false}
i = 0
print("\n bfs :")
self.bfs(point, visit)
while (i < @size)
if (visit[i] == false)
self.bfs(i, visit)
end
i += 1
end
end
end
def main()
# Number of nodes
totalNode = 7
g = MyGraph.new(totalNode)
# Connected two node with Edges
g.add_edge(0, 1)
g.add_edge(0, 5)
g.add_edge(2, 1)
g.add_edge(2, 6)
g.add_edge(3, 2)
g.add_edge(3, 4)
g.add_edge(4, 5)
g.add_edge(6, 0)
g.add_edge(6, 5)
g.print_graph()
# Start location
start = 6
g.view_bfs(start)
end
main()
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs :6 0 5 1 2 3 4
// Scala program
// Perform bfs in disconnected graph
class AjlistNode(var id: Int,
var next: AjlistNode) {
def this(value: Int) {
this(value,null);
}
}
class Vertices(var data: Int,
var next: AjlistNode) {
def this(value: Int) {
this(value,null);
}
}
class MyQueue(var element: Int,
var next: MyQueue) {
def this(value: Int) {
this(value,null);
}
}
class MyGraph(var size: Int,
var node: Array[Vertices],
var front: MyQueue,
var tail: MyQueue) {
def this(value: Int) {
//set value
this(value,Array.fill[Vertices](value)(null),null,null);
//set initial values of graph node
this.set_data();
}
//Set initial node value
def set_data(): Unit = {
if (this.node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < this.size) {
this.node(index) = new Vertices(index);
index += 1;
}
}
}
//Connect two node
def add_edge(start: Int, last: Int): Unit = {
var newEdge: AjlistNode = new AjlistNode(last);
if (this.node(start).next == null) {
//Include first adjacency list node of location start
this.node(start).next = newEdge;
} else {
var temp: AjlistNode = this.node(start).next;
//Add new node at the end of edge
while (temp.next != null) {
temp = temp.next;
}
//Add node
temp.next = newEdge;
}
}
//Display graph elements
def print_graph(): Unit = {
if (this.size > 0 &&
this.node != null) {
var index: Int = 0;
while (index < this.size) {
print("\nAdjacency list of vertex " + index + " : ");
var temp: AjlistNode = this.node(index).next;
while (temp != null) {
print(" "+this.node(temp.id).data + " ");
temp = temp.next;
}
index += 1;
}
}
}
def enqueue(value: Int): Unit = {
var newNode: MyQueue = new MyQueue(value);
if (newNode != null) {
if (this.front == null) {
this.front = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
} else {
print("\n Memory overflow");
}
}
def dequeue(): Unit = {
var temp: MyQueue = this.front;
this.front = temp.next;
if (this.tail == temp) {
this.tail = null;
}
temp = null;
}
def bfs(point: Int, visit: Array[Boolean]): Unit = {
var temp: AjlistNode = null;
enqueue(point);
while (this.front != null) {
temp = this.node(this.front.element).next;
while (temp != null) {
if (visit(temp.id) == false) {
visit(temp.id) = true;
enqueue(temp.id);
}
temp = temp.next;
}
visit(this.front.element) = true;
print(" "+this.front.element );
dequeue();
}
}
def view_bfs(point: Int): Unit = {
if (point > this.size ||
this.node == null) {
return;
}
var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
var i: Int = 0;
print("\n bfs : ");
bfs(point, visit);
while (i < this.size) {
if (visit(i) == false) {
bfs(i, visit);
}
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
//Number of nodes
var totalNode: Int = 7;
var g: MyGraph = new MyGraph(totalNode);
//Connected two node with Edges
g.add_edge(0, 1);
g.add_edge(0, 5);
g.add_edge(2, 1);
g.add_edge(2, 6);
g.add_edge(3, 2);
g.add_edge(3, 4);
g.add_edge(4, 5);
g.add_edge(6, 0);
g.add_edge(6, 5);
g.print_graph();
//Start location
var start: Int = 6;
g.view_bfs(start);
}
}
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs : 6 0 5 1 2 3 4
// Swift program
// Perform bfs in disconnected graph
class AjlistNode {
//Vertices node key
var id: Int;
var next: AjlistNode? ;
init(_ value: Int) {
//Set value of node key
self.id = value;
self.next = nil;
}
}
class Vertices {
var data: Int;
var next: AjlistNode? ;
init(_ value: Int) {
self.data = value;
self.next = nil;
}
}
class MyQueue {
var element: Int;
var next: MyQueue? ;
init(_ value: Int) {
self.element = value;
self.next = nil;
}
}
class MyGraph {
//number of Vertices
var size: Int;
var node: [Vertices]? = [Vertices]() ;
var front: MyQueue? ;
var tail: MyQueue? ;
init(_ value: Int) {
//set value
self.front = nil;
self.tail = nil;
self.size = value;
var i = 0;
while (i<value) {
self.node!.append(Vertices(i));
i+=1;
}
}
//Connect two node
func add_edge(_ start: Int, _ last: Int) {
let newEdge: AjlistNode? = AjlistNode(last);
if (self.node![start].next == nil) {
//Include first adjacency list node of location start
self.node![start].next = newEdge;
} else {
var temp: AjlistNode? = self.node![start].next;
//Add new node at the end of edge
while (temp!.next != nil) {
temp = temp!.next;
}
//Add node
temp!.next = newEdge;
}
}
//Display graph elements
func print_graph() {
if (self.size > 0 &&
self.node != nil) {
var index: Int = 0;
while (index < self.size) {
print("\nAdjacency list of vertex ", index ," : ", terminator : "");
var temp: AjlistNode? = self.node![index].next;
while (temp != nil) {
print(self.node![temp!.id].data ," ", terminator : "");
temp = temp!.next;
}
index += 1;
}
}
}
func enqueue(_ value: Int) {
let newNode: MyQueue? = MyQueue(value);
if (newNode != nil) {
if (self.front == nil) {
self.front = newNode;
self.tail = newNode;
} else {
self.tail!.next = newNode;
self.tail = newNode;
}
} else {
print("\n Memory overflow", terminator : "");
}
}
func dequeue() {
var temp: MyQueue? = self.front;
self.front = temp!.next;
if (self.tail === temp) {
self.tail = nil;
}
temp = nil;
}
func bfs(_ point: Int, _ visit: inout[Bool]) {
var temp: AjlistNode? = nil;
self.enqueue(point);
while (self.front != nil) {
temp = self.node![self.front!.element].next;
while (temp != nil) {
if (visit[temp!.id] == false) {
visit[temp!.id] = true;
self.enqueue(temp!.id);
}
temp = temp!.next;
}
visit[self.front!.element] = true;
print(self.front!.element ," ", terminator : "");
self.dequeue();
}
}
func view_bfs(_ point: Int) {
if (point > self.size ||
self.node == nil) {
return;
}
var visit: [Bool] = Array(repeating: false, count: self.size);
var i: Int = 0;
print("\n bfs : ", terminator : "");
self.bfs(point, &visit);
while (i < self.size) {
if (visit[i] == false) {
self.bfs(i, &visit);
}
i += 1;
}
}
}
func main() {
//Number of nodes
let totalNode: Int = 7;
let g: MyGraph? = MyGraph(totalNode);
//Connected two node with Edges
g!.add_edge(0, 1);
g!.add_edge(0, 5);
g!.add_edge(2, 1);
g!.add_edge(2, 6);
g!.add_edge(3, 2);
g!.add_edge(3, 4);
g!.add_edge(4, 5);
g!.add_edge(6, 0);
g!.add_edge(6, 5);
g!.print_graph();
//Start location
let start: Int = 6;
g!.view_bfs(start);
}
main();
Output
Adjacency list of vertex 0 : 1 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 1 6
Adjacency list of vertex 3 : 2 4
Adjacency list of vertex 4 : 5
Adjacency list of vertex 5 :
Adjacency list of vertex 6 : 0 5
bfs : 6 0 5 1 2 3 4
Time Complexity
In the worst case, we run BFS for each vertex in the graph. For each BFS traversal, the time complexity remains O(V + E), where V is the number of vertices and E is the number of edges in the subgraph. Therefore, the time complexity of executing BFS in a disconnected graph is O(V * (V + E)).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment