Posted on by Kalkicode
Code Graph

Count number of subgraphs in a graph

The problem you're addressing is about counting the number of subgraphs in a given graph. A subgraph is a subset of the vertices and edges of the original graph that forms a connected component. Your goal is to create a program that counts and outputs the number of subgraphs in the graph.

Problem Statement and Example

Given a graph with vertices and edges, you want to determine the number of subgraphs it contains. A subgraph is a portion of the graph that is connected within itself. For example, consider the following graph:

``````Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Edges: (0,1), (1,5), (2,3), (2,4), (6,7), (7,8), (7,12), (9,10)``````

You need to count how many subgraphs are present in this graph.

Idea to Solve

To solve this problem, you need to perform a Depth-First Search (DFS) traversal on the graph. The idea is to start from each unvisited vertex and perform a DFS to explore the connected component. The number of times you start a DFS will correspond to the number of subgraphs in the graph.

Pseudocode

``````function dfs(visited, start)
mark start as visited
for each neighbor of start
if neighbor is not visited
dfs(visited, neighbor)

function countSubGraph()
initialize visited array
mark all vertices as not visited
initialize result as 0
for each vertex i
if vertex i is not visited
increment result by 1
perform dfs(visited, i)
print result``````

Algorithm Explanation

1. The `dfs` function marks vertices as visited using Depth-First Search.
2. The `countSubGraph` function performs the following steps:
• Initialize the visited array.
• Mark all vertices as not visited.
• Initialize the result as 0.
• For each vertex, if it's not visited, increment the result by 1 and perform DFS.
• Print the final result.

Code Solution

``````// 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)
{
}
}
{
if (u < 0 || u >= this->vertices || v < 0 || v >= this->vertices)
{
return;
}
}
// 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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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)
{
}
}
public void addEdge(int u, int v)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
public void printGraph()
{
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++)
{
}
}
}
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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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
}
func getGraph(vertices int) * Graph {
var me *Graph = &Graph {}
me.vertices = vertices
return me
}
func(this Graph) addEdge(u, v int) {
if u < 0 || u >= this.vertices || v < 0 || v >= this.vertices {
return
}
}
// Display graph nodes and edges
func(this Graph) printGraph() {
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++ {
}
}
}
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
// When edge node not visiting, then perform DFS operation
}
// 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)
// 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)
{
}
}
public void addEdge(int u, int v)
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
public void printGraph()
{
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++)
{
}
}
}
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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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	function __construct(\$vertices)
{
\$this->vertices = \$vertices;
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
}
}
{
if (\$u < 0 || \$u >= \$this->vertices || \$v < 0
|| \$v >= \$this->vertices)
{
return;
}
}
// Display graph nodes and edges
public	function printGraph()
{
for (\$i = 0; \$i < \$this->vertices; ++\$i)
{
echo(" \n [".\$i.
"] :");
// iterate edges of i node
for (\$j = 0; \$j < count(\$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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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;
for (var i = 0; i < this.vertices; ++i)
{
}
}
{
if (u < 0 || u >= this.vertices
|| v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
printGraph()
{
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++)
{
}
}
}
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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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
i = 0
while (i < self.vertices) :
i += 1

if (u < 0 or u >= self.vertices or
v < 0 or v >= self.vertices) :
return

#  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
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
#  When edge node not visiting, then perform DFS operation

#  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)
#  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
#  Number of vertices in graph
#  Use to collect edges information
def initialize(vertices)
self.vertices = vertices
i = 0
while (i < self.vertices)
i += 1
end

end

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

end

#  Display graph nodes and edges
def printGraph()
i = 0
while (i < self.vertices)
print(" \n [", i ,"] :")
j = 0
#  iterate edges of i node
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
#  When edge node not visiting, then perform DFS operation
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)
#  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
{
def this(vertices: Int)
{
this(vertices, new ArrayBuffer[ArrayBuffer[Int]](vertices));
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
def addEdge(u: Int, v: Int): Unit = {
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
def printGraph(): Unit = {
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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
init(_ vertices: Int)
{
self.vertices = vertices;
var i: Int = 0;
while (i < self.vertices)
{
i += 1;
}
}
func addEdge(_ u: Int, _ v: Int)
{
if (u < 0 || u >= self.vertices || v < 0 || v >= self.vertices)
{
return;
}
}
// 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
{
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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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;
var i: Int = 0;
while (i < this.vertices)
{
i += 1;
}
}
fun addEdge(u: Int, v: Int): Unit
{
if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
{
return;
}
}
// Display graph nodes and edges
fun printGraph(): Unit
{
var i: Int = 0;
while (i < this.vertices)
{
print(" \n [" + i + "] :");
var j: Int = 0;
// iterate edges of i node
{
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
{
{
// When edge node not visiting, then perform DFS operation
}
// 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);
// 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``````

Time Complexity

The time complexity of the algorithm depends on the number of vertices and edges in the graph. The DFS traversal has a time complexity of O(V + E), where 'V' is the number of vertices and 'E' is the number of edges. The loop that iterates through each vertex contributes O(V) to the time complexity.

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.

Categories
Relative Post