Connected Components in an undirected graph

Posted on | Edited on | Views:

link

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
64
65
66
67
68
69
// import java.util.*;
class Graph { 
	// A user define class to represent a graph. 
	// A graph is an array of adjacency lists. 
	// Size of array will be V (number of vertices in graph) 
	int V; 
	LinkedList<Integer>[] adjListArray; 
	
	// constructor 
	Graph(int V) { 
		this.V = V; 
		// define the size of array as 
		// number of vertices 
		adjListArray = new LinkedList[V]; 

		// Create a new list for each vertex 
		// such that adjacent nodes can be stored 

		for(int i = 0; i < V ; i++){ 
			adjListArray[i] = new LinkedList<Integer>(); 
		} 
	} 
	
	// Adds an edge to an undirected graph 
	void addEdge( int src, int dest) { 
		// Add an edge from src to dest. 
		adjListArray[src].add(dest); 
		// Since graph is undirected, add an edge from dest 
		// to src also 
		adjListArray[dest].add(src); 
	} 
	
	void DFSUtil(int v, boolean[] visited) { 
		// Mark the current node as visited and print it 
		visited[v] = true; 
		System.out.print(v+" "); 
		// Recur for all the vertices 
		// adjacent to this vertex 
		for (int x : adjListArray[v]) { 
			if(!visited[x]) DFSUtil(x,visited); 
		} 

	} 
	void connectedComponents() { 
		// Mark all the vertices as not visited 
		boolean[] visited = new boolean[V]; 
		for(int v = 0; v < V; ++v) { 
			if(!visited[v]) { 
				// print all reachable vertices from v 
				DFSUtil(v,visited); 
				System.out.println(); 
			} 
		} 
	} 
}	 
/*
public class MyClass {	
	// Driver program to test above 
	public static void main(String[] args){ 
		// Create a graph given in the above diagram 
		Graph g = new Graph(5); // 5 vertices numbered from 0 to 4 
		
		g.addEdge(1, 0); 
		g.addEdge(2, 3); 
		g.addEdge(3, 4); 
		System.out.println("Following are connected components"); 
		g.connectedComponents(); 
	} 
}*/

0%