Skip to main content

Count number of subgraphs in a graph

Here given code implementation process.

Subgraph of a graph networks 
// Include header file
#include <iostream>
#include <vector>
using namespace std;

/*
    C++ Program
    Count number of subgraphs in a graph
*/

class Graph
{
	public:
	// Number of vertices in graph
	int vertices;
	// Use to collect edges information
	vector < vector < int > > adjacencylist;
	Graph(int vertices)
	{
		this->vertices = vertices;
		for (int i = 0; i < this->vertices; ++i)
		{
			this->adjacencylist.push_back(vector < int > ());
		}
	}
	void addEdge(int u, int v)
	{
		if (u < 0 || u >= this->vertices || v < 0 || v >= this->vertices)
		{
			return;
		}
		// Add node edge
		this->adjacencylist.at(u).push_back(v);
		this->adjacencylist.at(v).push_back(u);
	}
	// Display graph nodes and edges
	void printGraph()
	{
		cout << "\n Graph Adjacency List ";
		for (int i = 0; i < this->vertices; ++i)
		{
			cout << " \n [" << i << "] :";
			// iterate edges of i node
			for (int j = 0; j < this->adjacencylist.at(i).size(); j++)
			{
				cout << "  " << this->adjacencylist.at(i).at(j);
			}
		}
	}
	void dfs(bool visited[], int start)
	{
		if (start < 0 || start >= this->vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		int i = 0;
		// Execute edges of given start vertices
		while (i < this->adjacencylist.at(start).size())
		{
			if (visited[this->adjacencylist.at(start).at(i)] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this->dfs(visited, this->adjacencylist.at(start).at(i));
			}
			// Visit to next node
			i++;
		}
	}
	void countSubGraph()
	{
		bool visited[this->vertices];
		int result = 0;
		for (int i = 0; i < this->vertices; ++i)
		{
			visited[i] = false;
		}
		for (int i = 0; i < this->vertices; ++i)
		{
			if (visited[i] == false)
			{
				// When node is not visiting
				result++;
				// perform dfs (start vertices i)
				this->dfs(visited, i);
			}
		}
		// Display calculated result
		cout << "\n Number of subgraphs is : " << result;
	}
};
int main()
{
	Graph *g = new Graph(13);
	g->addEdge(0, 1);
	g->addEdge(1, 5);
	g->addEdge(2, 3);
	g->addEdge(2, 4);
	g->addEdge(6, 7);
	g->addEdge(7, 8);
	g->addEdge(7, 12);
	g->addEdge(9, 10);
	// Display graph element
	g->printGraph();
	// Display number of subgraphs
	g->countSubGraph();
	return 0;
}

input

 Graph Adjacency List
 [0] :  1
 [1] :  0  5
 [2] :  3  4
 [3] :  2
 [4] :  2
 [5] :  1
 [6] :  7
 [7] :  6  8  12
 [8] :  7
 [9] :  10
 [10] :  9
 [11] :
 [12] :  7
 Number of subgraphs is : 5
import java.util.ArrayList;
/*
    Java Program
    Count number of subgraphs in a graph
*/
public class Graph
{
	// Number of vertices in graph
	public int vertices;
	// Use to collect edges information
	public ArrayList < ArrayList < Integer >> adjacencylist;
	public Graph(int vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = new ArrayList < ArrayList < Integer >> (vertices);
		for (int i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.add(new ArrayList < Integer > ());
		}
	}
	public void addEdge(int u, int v)
	{
		if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		adjacencylist.get(u).add(v);
		adjacencylist.get(v).add(u);
	}
	// Display graph nodes and edges
	public void printGraph()
	{
		System.out.print("\n Graph Adjacency List ");
		for (int i = 0; i < this.vertices; ++i)
		{
			System.out.print(" \n [" + i + "] :");
			// iterate edges of i node
			for (int j = 0; j < this.adjacencylist.get(i).size(); j++)
			{
				System.out.print("  " + this.adjacencylist.get(i).get(j));
			}
		}
	}
	public void dfs(boolean[] visited, int start)
	{
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		int i = 0;
		// Execute edges of given start vertices
		while (i < adjacencylist.get(start).size())
		{
			if (visited[adjacencylist.get(start).get(i)] == false)
			{
				// When edge node not visiting, then perform DFS operation
				dfs(visited, adjacencylist.get(start).get(i));
			}
			// Visit to next node
			i++;
		}
	}
	public void countSubGraph()
	{
		boolean[] visited = new boolean[this.vertices];
		int result = 0;
		for (int i = 0; i < this.vertices; ++i)
		{
			visited[i] = false;
		}
		for (int i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				// When node is not visiting
				result++;
				// perform dfs (start vertices i)
				dfs(visited, i);
			}
		}
		// Display calculated result
		System.out.print("\n Number of subgraphs is : " + result);
	}
	public static void main(String[] args)
	{
		Graph g = new Graph(13);
		g.addEdge(0, 1);
		g.addEdge(1, 5);
		g.addEdge(2, 3);
		g.addEdge(2, 4);
		g.addEdge(6, 7);
		g.addEdge(7, 8);
		g.addEdge(7, 12);
		g.addEdge(9, 10);
		// Display graph element
		g.printGraph();
		// Display number of subgraphs
		g.countSubGraph();
	}
}

input

 Graph Adjacency List
 [0] :  1
 [1] :  0  5
 [2] :  3  4
 [3] :  2
 [4] :  2
 [5] :  1
 [6] :  7
 [7] :  6  8  12
 [8] :  7
 [9] :  10
 [10] :  9
 [11] :
 [12] :  7
 Number of subgraphs is : 5
package main
import "fmt"
/*
    Go Program
    Count number of subgraphs in a graph
*/
type Graph struct {
	// Number of vertices in graph
	vertices int
	// Use to collect edges information
	adjacencylist [][]int
}
func getGraph(vertices int) * Graph {
	var me *Graph = &Graph {}
	me.vertices = vertices
	me.adjacencylist = make([][]int,vertices)
	return me
}
func(this Graph) addEdge(u, v int) {
	if u < 0 || u >= this.vertices || v < 0 || v >= this.vertices {
		return
	}
	// Add node edge
	this.adjacencylist[u] = append(this.adjacencylist[u], v)
	this.adjacencylist[v] = append(this.adjacencylist[v], u)
}
// Display graph nodes and edges
func(this Graph) printGraph() {
	fmt.Print("\n Graph Adjacency List ")
	for i := 0 ; i < this.vertices ; i++ {
		fmt.Print(" \n [", i, "] :")
		// iterate edges of i node
		for j := 0 ; j < len(this.adjacencylist[i]) ; j++ {
			fmt.Print("  ", this.adjacencylist[i][j])
		}
	}
}
func(this Graph) dfs(visited[] bool, start int) {
	if start < 0 || start >= this.vertices {
		// In case given invalid node
		return
	}
	// Mark a current visited node
	visited[start] = true
	var i int = 0
	// Execute edges of given start vertices
	for (i < len(this.adjacencylist[start])) {
		if visited[this.adjacencylist[start][i]] == false {
			// When edge node not visiting, then perform DFS operation
			this.dfs(visited, this.adjacencylist[start][i])
		}
		// Visit to next node
		i++
	}
}
func(this Graph) countSubGraph() {
	var visited = make([]bool,this.vertices)
	var result int = 0
	for i := 0 ; i < this.vertices ; i++ {
		visited[i] = false
	}
	for i := 0 ; i < this.vertices ; i++ {
		if visited[i] == false {
			// When node is not visiting
			result++
			// perform dfs (start vertices i)
			this.dfs(visited, i)
		}
	}
	// Display calculated result
	fmt.Print("\n Number of subgraphs is : ", result)
}
func main() {
	var g * Graph = getGraph(13)
	g.addEdge(0, 1)
	g.addEdge(1, 5)
	g.addEdge(2, 3)
	g.addEdge(2, 4)
	g.addEdge(6, 7)
	g.addEdge(7, 8)
	g.addEdge(7, 12)
	g.addEdge(9, 10)
	// Display graph element
	g.printGraph()
	// Display number of subgraphs
	g.countSubGraph()
}

input

 Graph Adjacency List  
 [0] :  1 
 [1] :  0  5 
 [2] :  3  4 
 [3] :  2 
 [4] :  2 
 [5] :  1 
 [6] :  7 
 [7] :  6  8  12 
 [8] :  7 
 [9] :  10 
 [10] :  9 
 [11] : 
 [12] :  7
 Number of subgraphs is : 5
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Count number of subgraphs in a graph
*/
public class Graph
{
	// Number of vertices in graph
	public int vertices;
	// Use to collect edges information
	public List < List < int >> adjacencylist;
	public Graph(int vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = new List < List < int >> (vertices);
		for (int i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.Add(new List < int > ());
		}
	}
	public void addEdge(int u, int v)
	{
		if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		this.adjacencylist[u].Add(v);
		this.adjacencylist[v].Add(u);
	}
	// Display graph nodes and edges
	public void printGraph()
	{
		Console.Write("\n Graph Adjacency List ");
		for (int i = 0; i < this.vertices; ++i)
		{
			Console.Write(" \n [" + i + "] :");
			// iterate edges of i node
			for (int j = 0; j < this.adjacencylist[i].Count; j++)
			{
				Console.Write("  " + this.adjacencylist[i][j]);
			}
		}
	}
	public void dfs(Boolean[] visited, int start)
	{
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		int i = 0;
		// Execute edges of given start vertices
		while (i < this.adjacencylist[start].Count)
		{
			if (visited[this.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this.dfs(visited, this.adjacencylist[start][i]);
			}
			// Visit to next node
			i++;
		}
	}
	public void countSubGraph()
	{
		Boolean[] visited = new Boolean[this.vertices];
		int result = 0;
		for (int i = 0; i < this.vertices; ++i)
		{
			visited[i] = false;
		}
		for (int i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				// When node is not visiting
				result++;
				// perform dfs (start vertices i)
				this.dfs(visited, i);
			}
		}
		// Display calculated result
		Console.Write("\n Number of subgraphs is : " + result);
	}
	public static void Main(String[] args)
	{
		Graph g = new Graph(13);
		g.addEdge(0, 1);
		g.addEdge(1, 5);
		g.addEdge(2, 3);
		g.addEdge(2, 4);
		g.addEdge(6, 7);
		g.addEdge(7, 8);
		g.addEdge(7, 12);
		g.addEdge(9, 10);
		// Display graph element
		g.printGraph();
		// Display number of subgraphs
		g.countSubGraph();
	}
}

input

 Graph Adjacency List
 [0] :  1
 [1] :  0  5
 [2] :  3  4
 [3] :  2
 [4] :  2
 [5] :  1
 [6] :  7
 [7] :  6  8  12
 [8] :  7
 [9] :  10
 [10] :  9
 [11] :
 [12] :  7
 Number of subgraphs is : 5
<?php
/*
    Php Program
    Count number of subgraphs in a graph
*/
class Graph
{
	// Number of vertices in graph
	public $vertices;
	// Use to collect edges information
	public $adjacencylist;
	public	function __construct($vertices)
	{
		$this->vertices = $vertices;
		$this->adjacencylist = array();
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			$this->adjacencylist[] = array();
		}
	}
	public	function addEdge($u, $v)
	{
		if ($u < 0 || $u >= $this->vertices || $v < 0 
            || $v >= $this->vertices)
		{
			return;
		}
		// Add node edge
		$this->adjacencylist[$u][] = $v;
		$this->adjacencylist[$v][] = $u;
	}
	// Display graph nodes and edges
	public	function printGraph()
	{
		echo("\n Graph Adjacency List ");
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			echo(" \n [".$i.
				"] :");
			// iterate edges of i node
			for ($j = 0; $j < count($this->adjacencylist[$i]); $j++)
			{
				echo("  ".$this->adjacencylist[$i][$j]);
			}
		}
	}
	public	function dfs(&$visited, $start)
	{
		if ($start < 0 || $start >= $this->vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		$visited[$start] = true;
		$i = 0;
		// Execute edges of given start vertices
		while ($i < count($this->adjacencylist[$start]))
		{
			if ($visited[$this->adjacencylist[$start][$i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				$this->dfs($visited, $this->adjacencylist[$start][$i]);
			}
			// Visit to next node
			$i++;
		}
	}
	public	function countSubGraph()
	{
		$visited = array_fill(0, $this->vertices, false);
		$result = 0;
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			$visited[$i] = false;
		}
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			if ($visited[$i] == false)
			{
				// When node is not visiting
				$result++;
				// perform dfs (start vertices i)
				$this->dfs($visited, $i);
			}
		}
		// Display calculated result
		echo("\n Number of subgraphs is : ".$result);
	}
}

function main()
{
	$g = new Graph(13);
	$g->addEdge(0, 1);
	$g->addEdge(1, 5);
	$g->addEdge(2, 3);
	$g->addEdge(2, 4);
	$g->addEdge(6, 7);
	$g->addEdge(7, 8);
	$g->addEdge(7, 12);
	$g->addEdge(9, 10);
	// Display graph element
	$g->printGraph();
	// Display number of subgraphs
	$g->countSubGraph();
}
main();

input

 Graph Adjacency List
 [0] :  1
 [1] :  0  5
 [2] :  3  4
 [3] :  2
 [4] :  2
 [5] :  1
 [6] :  7
 [7] :  6  8  12
 [8] :  7
 [9] :  10
 [10] :  9
 [11] :
 [12] :  7
 Number of subgraphs is : 5
/*
    Node JS Program
    Count number of subgraphs in a graph
*/
class Graph
{
	constructor(vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = [];
		for (var i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.push([]);
		}
	}
	addEdge(u, v)
	{
		if (u < 0 || u >= this.vertices 
            || v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		this.adjacencylist[u].push(v);
		this.adjacencylist[v].push(u);
	}
	// Display graph nodes and edges
	printGraph()
	{
		process.stdout.write("\n Graph Adjacency List ");
		for (var i = 0; i < this.vertices; ++i)
		{
			process.stdout.write(" \n [" + i + "] :");
			// iterate edges of i node
			for (var j = 0; j < this.adjacencylist[i].length; j++)
			{
				process.stdout.write("  " + this.adjacencylist[i][j]);
			}
		}
	}
	dfs(visited, start)
	{
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		var i = 0;
		// Execute edges of given start vertices
		while (i < this.adjacencylist[start].length)
		{
			if (visited[this.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this.dfs(visited, this.adjacencylist[start][i]);
			}
			// Visit to next node
			i++;
		}
	}
	countSubGraph()
	{
		var visited = Array(this.vertices).fill(false);
		var result = 0;
		for (var i = 0; i < this.vertices; ++i)
		{
			visited[i] = false;
		}
		for (var i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				// When node is not visiting
				result++;
				// perform dfs (start vertices i)
				this.dfs(visited, i);
			}
		}
		// Display calculated result
		process.stdout.write("\n Number of subgraphs is : " + result);
	}
}

function main()
{
	var g = new Graph(13);
	g.addEdge(0, 1);
	g.addEdge(1, 5);
	g.addEdge(2, 3);
	g.addEdge(2, 4);
	g.addEdge(6, 7);
	g.addEdge(7, 8);
	g.addEdge(7, 12);
	g.addEdge(9, 10);
	// Display graph element
	g.printGraph();
	// Display number of subgraphs
	g.countSubGraph();
}
main();

input

 Graph Adjacency List
 [0] :  1
 [1] :  0  5
 [2] :  3  4
 [3] :  2
 [4] :  2
 [5] :  1
 [6] :  7
 [7] :  6  8  12
 [8] :  7
 [9] :  10
 [10] :  9
 [11] :
 [12] :  7
 Number of subgraphs is : 5
#    Python 3 Program
#    Count number of subgraphs in a graph
class Graph :
	#  Number of vertices in graph
	#  Use to collect edges information
	def __init__(self, vertices) :
		self.vertices = vertices
		self.adjacencylist = []
		i = 0
		while (i < self.vertices) :
			self.adjacencylist.append([])
			i += 1
		
	
	def addEdge(self, u, v) :
		if (u < 0 or u >= self.vertices or 
            v < 0 or v >= self.vertices) :
			return
		
		#  Add node edge
		self.adjacencylist[u].append(v)
		self.adjacencylist[v].append(u)
	
	#  Display graph nodes and edges
	def printGraph(self) :
		print("\n Graph Adjacency List ", end = "")
		i = 0
		while (i < self.vertices) :
			print(" \n [", i ,"] :", end = "")
			j = 0
			#  iterate edges of i node
			while (j < len(self.adjacencylist[i])) :
				print("  ", self.adjacencylist[i][j], end = "")
				j += 1
			
			i += 1
		
	
	def dfs(self, visited, start) :
		if (start < 0 or start >= self.vertices) :
			#  In case given invalid node
			return
		
		#  Mark a current visited node
		visited[start] = True
		i = 0
		#  Execute edges of given start vertices
		while (i < len(self.adjacencylist[start])) :
			if (visited[self.adjacencylist[start][i]] == False) :
				#  When edge node not visiting, then perform DFS operation
				self.dfs(visited, self.adjacencylist[start][i])
			
			#  Visit to next node
			i += 1
		
	
	def countSubGraph(self) :
		visited = [False] * (self.vertices)
		result = 0
		i = 0
		while (i < self.vertices) :
			visited[i] = False
			i += 1
		
		i = 0
		while (i < self.vertices) :
			if (visited[i] == False) :
				#  When node is not visiting
				result += 1
				#  perform dfs (start vertices i)
				self.dfs(visited, i)
			
			i += 1
		
		#  Display calculated result
		print("\n Number of subgraphs is : ", result, end = "")
	

def main() :
	g = Graph(13)
	g.addEdge(0, 1)
	g.addEdge(1, 5)
	g.addEdge(2, 3)
	g.addEdge(2, 4)
	g.addEdge(6, 7)
	g.addEdge(7, 8)
	g.addEdge(7, 12)
	g.addEdge(9, 10)
	#  Display graph element
	g.printGraph()
	#  Display number of subgraphs
	g.countSubGraph()

if __name__ == "__main__": main()

input

 Graph Adjacency List
 [ 0 ] :   1
 [ 1 ] :   0   5
 [ 2 ] :   3   4
 [ 3 ] :   2
 [ 4 ] :   2
 [ 5 ] :   1
 [ 6 ] :   7
 [ 7 ] :   6   8   12
 [ 8 ] :   7
 [ 9 ] :   10
 [ 10 ] :   9
 [ 11 ] :
 [ 12 ] :   7
 Number of subgraphs is :  5
#    Ruby Program
#    Count number of subgraphs in a graph
class Graph 
	# Define the accessor and reader of class Graph
	attr_reader :vertices, :adjacencylist
	attr_accessor :vertices, :adjacencylist
	#  Number of vertices in graph
	#  Use to collect edges information
	def initialize(vertices) 
		self.vertices = vertices
		self.adjacencylist = []
		i = 0
		while (i < self.vertices) 
			self.adjacencylist.push([])
			i += 1
		end

	end

	def addEdge(u, v) 
		if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices) 
			return
		end

		#  Add node edge
		self.adjacencylist[u].push(v)
		self.adjacencylist[v].push(u)
	end

	#  Display graph nodes and edges
	def printGraph() 
		print("\n Graph Adjacency List ")
		i = 0
		while (i < self.vertices) 
			print(" \n [", i ,"] :")
			j = 0
			#  iterate edges of i node
			while (j < self.adjacencylist[i].length) 
				print("  ", self.adjacencylist[i][j])
				j += 1
			end

			i += 1
		end

	end

	def dfs(visited, start) 
		if (start < 0 || start >= self.vertices) 
			#  In case given invalid node
			return
		end

		#  Mark a current visited node
		visited[start] = true
		i = 0
		#  Execute edges of given start vertices
		while (i < self.adjacencylist[start].length) 
			if (visited[self.adjacencylist[start][i]] == false) 
				#  When edge node not visiting, then perform DFS operation
				self.dfs(visited, self.adjacencylist[start][i])
			end

			#  Visit to next node
			i += 1
		end

	end

	def countSubGraph() 
		visited = Array.new(self.vertices) {false}
		result = 0
		i = 0
		while (i < self.vertices) 
			visited[i] = false
			i += 1
		end

		i = 0
		while (i < self.vertices) 
			if (visited[i] == false) 
				#  When node is not visiting
				result += 1
				#  perform dfs (start vertices i)
				self.dfs(visited, i)
			end

			i += 1
		end

		#  Display calculated result
		print("\n Number of subgraphs is : ", result)
	end

end

def main() 
	g = Graph.new(13)
	g.addEdge(0, 1)
	g.addEdge(1, 5)
	g.addEdge(2, 3)
	g.addEdge(2, 4)
	g.addEdge(6, 7)
	g.addEdge(7, 8)
	g.addEdge(7, 12)
	g.addEdge(9, 10)
	#  Display graph element
	g.printGraph()
	#  Display number of subgraphs
	g.countSubGraph()
end

main()

input

 Graph Adjacency List  
 [0] :  1 
 [1] :  0  5 
 [2] :  3  4 
 [3] :  2 
 [4] :  2 
 [5] :  1 
 [6] :  7 
 [7] :  6  8  12 
 [8] :  7 
 [9] :  10 
 [10] :  9 
 [11] : 
 [12] :  7
 Number of subgraphs is : 5
import scala.collection.mutable._;
/*
    Scala Program
    Count number of subgraphs in a graph
*/
class Graph(
	// Number of vertices in graph
	var vertices: Int,
		// Use to collect edges information
		var adjacencylist: ArrayBuffer[ArrayBuffer[Int]])
{
	def this(vertices: Int)
	{
		this(vertices, new ArrayBuffer[ArrayBuffer[Int]](vertices));
		var i: Int = 0;
		while (i < this.vertices)
		{
			this.adjacencylist += new ArrayBuffer[Int]();
			i += 1;
		}
	}
	def addEdge(u: Int, v: Int): Unit = {
		if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		adjacencylist(u) += v;
		adjacencylist(v) += u;
	}
	// Display graph nodes and edges
	def printGraph(): Unit = {
		print("\n Graph Adjacency List ");
		var i: Int = 0;
		while (i < this.vertices)
		{
			print(" \n [" + i + "] :");
			var j: Int = 0;
			// iterate edges of i node
			while (j < this.adjacencylist(i).size)
			{
				print("  " + this.adjacencylist(i)(j));
				j += 1;
			}
			i += 1;
		}
	}
	def dfs(visited: Array[Boolean], start: Int): Unit = {
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited(start) = true;
		var i: Int = 0;
		// Execute edges of given start vertices
		while (i < adjacencylist(start).size)
		{
			if (visited(adjacencylist(start)(i)) == false)
			{
				// When edge node not visiting, then perform DFS operation
				dfs(visited, adjacencylist(start)(i));
			}
			// Visit to next node
			i += 1;
		}
	}
	def countSubGraph(): Unit = {
		var visited: Array[Boolean] = 
          Array.fill[Boolean](this.vertices)(false);
		var result: Int = 0;
		var i: Int = 0;
		while (i < this.vertices)
		{
			visited(i) = false;
			i += 1;
		}
		i = 0;
		while (i < this.vertices)
		{
			if (visited(i) == false)
			{
				// When node is not visiting
				result += 1;
				// perform dfs (start vertices i)
				dfs(visited, i);
			}
			i += 1;
		}
		// Display calculated result
		print("\n Number of subgraphs is : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var g: Graph = new Graph(13);
		g.addEdge(0, 1);
		g.addEdge(1, 5);
		g.addEdge(2, 3);
		g.addEdge(2, 4);
		g.addEdge(6, 7);
		g.addEdge(7, 8);
		g.addEdge(7, 12);
		g.addEdge(9, 10);
		// Display graph element
		g.printGraph();
		// Display number of subgraphs
		g.countSubGraph();
	}
}

input

 Graph Adjacency List
 [0] :  1
 [1] :  0  5
 [2] :  3  4
 [3] :  2
 [4] :  2
 [5] :  1
 [6] :  7
 [7] :  6  8  12
 [8] :  7
 [9] :  10
 [10] :  9
 [11] :
 [12] :  7
 Number of subgraphs is : 5
import Foundation;
/*
    Swift 4 Program
    Count number of subgraphs in a graph
*/
class Graph
{
	// Number of vertices in graph
	var vertices: Int;
	// Use to collect edges information
	var adjacencylist: [[Int]];
	init(_ vertices: Int)
	{
		self.vertices = vertices;
		self.adjacencylist = [[Int]]();
		var i: Int = 0;
		while (i < self.vertices)
		{
			self.adjacencylist.append([Int]());
			i += 1;
		}
	}
	func addEdge(_ u: Int, _ v: Int)
	{
		if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices)
		{
			return;
		}
		// Add node edge
		self.adjacencylist[u].append(v);
		self.adjacencylist[v].append(u);
	}
	// Display graph nodes and edges
	func printGraph()
	{
		print("\n Graph Adjacency List ", terminator: "");
		var i: Int = 0;
		while (i < self.vertices)
		{
			print(" \n [", i ,"] :", terminator: "");
			var j: Int = 0;
			// iterate edges of i node
			while (j < self.adjacencylist[i].count)
			{
				print("  ", self.adjacencylist[i][j], terminator: "");
				j += 1;
			}
			i += 1;
		}
	}
	func dfs(_ visited: inout[Bool], _ start: Int)
	{
		if (start < 0 || start >= self.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		var i: Int = 0;
		// Execute edges of given start vertices
		while (i < self.adjacencylist[start].count)
		{
			if (visited[self.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				self.dfs(&visited, self.adjacencylist[start][i]);
			}
			// Visit to next node
			i += 1;
		}
	}
	func countSubGraph()
	{
		var visited: [Bool] = Array(repeating: false, count: self.vertices);
		var result: Int = 0;
		var i: Int = 0;
		while (i < self.vertices)
		{
			if (visited[i] == false)
			{
				// When node is not visiting
				result += 1;
				// perform dfs (start vertices i)
				self.dfs(&visited, i);
			}
			i += 1;
		}
		// Display calculated result
		print("\n Number of subgraphs is : ", result, terminator: "");
	}
}
func main()
{
	let g: Graph = Graph(13);
	g.addEdge(0, 1);
	g.addEdge(1, 5);
	g.addEdge(2, 3);
	g.addEdge(2, 4);
	g.addEdge(6, 7);
	g.addEdge(7, 8);
	g.addEdge(7, 12);
	g.addEdge(9, 10);
	// Display graph element
	g.printGraph();
	// Display number of subgraphs
	g.countSubGraph();
}
main();

input

 Graph Adjacency List
 [ 0 ] :   1
 [ 1 ] :   0   5
 [ 2 ] :   3   4
 [ 3 ] :   2
 [ 4 ] :   2
 [ 5 ] :   1
 [ 6 ] :   7
 [ 7 ] :   6   8   12
 [ 8 ] :   7
 [ 9 ] :   10
 [ 10 ] :   9
 [ 11 ] :
 [ 12 ] :   7
 Number of subgraphs is :  5
/*
    Kotlin Program
    Count number of subgraphs in a graph
*/
class Graph
{
	// Number of vertices in graph
	var vertices: Int;
	// Use to collect edges information
	var adjacencylist: MutableList < MutableList < Int >> ;
	constructor(vertices: Int)
	{
		this.vertices = vertices;
		this.adjacencylist = mutableListOf<MutableList<Int>>();
		var i: Int = 0;
		while (i < this.vertices)
		{
			this.adjacencylist.add(mutableListOf < Int > ());
			i += 1;
		}
	}
	fun addEdge(u: Int, v: Int): Unit
	{
		if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		this.adjacencylist[u].add(v);
		this.adjacencylist[v].add(u);
	}
	// Display graph nodes and edges
	fun printGraph(): Unit
	{
		print("\n Graph Adjacency List ");
		var i: Int = 0;
		while (i < this.vertices)
		{
			print(" \n [" + i + "] :");
			var j: Int = 0;
			// iterate edges of i node
			while (j < this.adjacencylist[i].size)
			{
				print("  " + this.adjacencylist[i][j]);
				j += 1;
			}
			i += 1;
		}
	}
	fun dfs(visited: Array < Boolean > , start: Int): Unit
	{
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		var i: Int = 0;
		// Execute edges of given start vertices
		while (i < this.adjacencylist[start].size)
		{
			if (visited[this.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this.dfs(visited, this.adjacencylist[start][i]);
			}
			// Visit to next node
			i += 1;
		}
	}
	fun countSubGraph(): Unit
	{
		var visited: Array < Boolean > = Array(this.vertices)
		{
			false
		};
		var result: Int = 0;
		var i: Int = 0;
		while (i < this.vertices)
		{
			if (visited[i] == false)
			{
				// When node is not visiting
				result += 1;
				// perform dfs (start vertices i)
				this.dfs(visited, i);
			}
			i += 1;
		}
		// Display calculated result
		print("\n Number of subgraphs is : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val g: Graph = Graph(13);
	g.addEdge(0, 1);
	g.addEdge(1, 5);
	g.addEdge(2, 3);
	g.addEdge(2, 4);
	g.addEdge(6, 7);
	g.addEdge(7, 8);
	g.addEdge(7, 12);
	g.addEdge(9, 10);
	// Display graph element
	g.printGraph();
	// Display number of subgraphs
	g.countSubGraph();
}

input

 Graph Adjacency List
 [0] :  1
 [1] :  0  5
 [2] :  3  4
 [3] :  2
 [4] :  2
 [5] :  1
 [6] :  7
 [7] :  6  8  12
 [8] :  7
 [9] :  10
 [10] :  9
 [11] :
 [12] :  7
 Number of subgraphs is : 5
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