Skip to main content

Execute BFS in disconnected graph

BFS (Breadth-First Search) is a graph traversal algorithm that is used to traverse all the vertices of a graph in a breadth-first order. When a graph is disconnected, it means that there are one or more vertices that are not reachable from other vertices in the graph.

When you want to execute BFS on a disconnected graph, you need to perform BFS on each connected component of the graph separately. A connected component is a subset of vertices in a graph such that there is a path between any two vertices in the subset.

To execute BFS in a disconnected graph, you can follow these steps:

  1. Initialize all vertices as not visited.
  2. For each vertex v that is not visited, do the following: a. Initialize an empty queue. b. Mark vertex v as visited and add it to the queue. c. While the queue is not empty, do the following: i. Remove the first vertex from the queue and print it. ii. Add all adjacent vertices of the removed vertex to the queue if they are not visited and mark them as visited. d. When the queue becomes empty, it means that you have visited all the vertices in the connected component.
  3. Repeat step 2 for any remaining vertices that are not visited.

By performing BFS on each connected component separately, you can traverse all the vertices in a disconnected graph.

//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
Last updated on by Kalkicode




Comment

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