Count number of subgraphs in a graph
Here given code implementation process.

// 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
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