-
Notifications
You must be signed in to change notification settings - Fork 0
/
CountOfConnectedComponentsGraphUsingDFS.java
64 lines (50 loc) · 1.5 KB
/
CountOfConnectedComponentsGraphUsingDFS.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package com.ttahb.graph;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
/**
* Counts the number of disconnected components in a graph with 'v' vertices. It uses a recursive DFS
* method to travers each component.
*
* @author - bhattvijay69@hotmail.com
*/
public class CountOfConnectedComponentsGraphUsingDFS {
private final List<ArrayList<Integer>> adjList;
private final boolean[] visited;
private static int count = 0;
/**
* @param v - number of total vertices.
*/
public CountOfConnectedComponentsGraphUsingDFS(int v) {
// using Streams to generate a list of list [[],[],[],[],[]] based on 'v' passed.
adjList = Stream.generate(ArrayList<Integer>::new).limit(v).toList();
visited = new boolean[v];
}
public void addEdge(int x, int y) {
adjList.get(x).add(y);
adjList.get(y).add(x);
}
/**
* Dummy method to accept graph component with only 1 isolated node.
*
* @param x
*/
public void addEdge(int x) {
}
public int countConnectedComponents() {
for (int i = 0; i < adjList.size(); i++) {
if (!visited[i]) {
depthFirstSearch(i);
count++;
}
}
return count;
}
public void depthFirstSearch(int v) {
if (visited[v])
return;
visited[v] = true;
List<Integer> neighbours = adjList.get(v);
neighbours.forEach(this::depthFirstSearch);
}
}