All Connected Components Using Breadth-First Search

This is an implementation of the problem: Determining All Connected Components in a Graph using Breadth-First Search. The implementation can support any type of nodes (i.e. String, Integer, etc.).

According to Wikipedia (2012), the set of nodes reached by a BFS (breadth-first search) form the connected component containing the starting node.

This implementation uses a Queue to find all connected components of a particular source node.

The Graph implementation can be found here.

GraphConnectedBFS.java

import java.util.*;
import java.io.*;

// Written by: Yancy Vance M. Paredes.

// Determining all connected components in a graph using BFS.

public class GraphConnectedBFS {

	public static void main(String[] args) throws Exception {
		Scanner iFile = new Scanner(new FileReader("connectedBFS.in"));
		Graph graph = new Graph();
		graph.setUndirected();
		graph.setSortedNeighbors(true);

		while(iFile.hasNext()) {
			Node<String> a = new Node<String>(iFile.next());
			Node<String> b = new Node<String>(iFile.next());

			int aPos = graph.indexOf(a);
			int bPos = graph.indexOf(b);

			// If a does not exist in the graph yet.
			if(aPos == -1)
				aPos = graph.addNode(a);

			// If b does not exist in the graph yet.
			if(bPos == -1)
				bPos = graph.addNode(b);

			Edge edge = new Edge(graph.getNodeAt(aPos), graph.getNodeAt(bPos));

			graph.addEdge(edge);
		}

		//graph.printNodes();
		//graph.printEdges();

		Vector<Node> nodes = graph.getNodes();

		// Use all the different nodes as the root or source node.
		for(int i = 0; i < nodes.size(); i++) {
			// Do a Breadth-First Search.
			Node start = nodes.elementAt(i);
			Queue<Node> queue = new LinkedList<Node>();

			queue.add(start);
			start.visit();

			System.out.println("From: " + start + ", you can visit: ");
			System.out.print("\t");

			while(!queue.isEmpty()) {
				Node temp = queue.remove();

				Vector<Node> neighbors = graph.getNeighbors(temp);

				for(int j = 0; j < neighbors.size(); j++)
					if(!neighbors.elementAt(j).isVisited()) {
						neighbors.elementAt(j).visit();
						queue.add(neighbors.elementAt(j));
					}

				System.out.print(temp + ", ");
			}

			System.out.println();

			// Remove all the visited flags.
			graph.unvisitAllNodes();
		}

		iFile.close();
	}

}

connectedBFS.in

roxas claveria
san_pedro roxas
claveria san_pedro
ponciano san_pedro
talomo ulas
ulas puan
mintal makilala

The input file describes an undirected connection between two places.

Sample Output:

From: roxas, you can visit: 
	roxas, claveria, san_pedro, ponciano, 
From: claveria, you can visit: 
	claveria, roxas, san_pedro, ponciano, 
From: san_pedro, you can visit: 
	san_pedro, claveria, ponciano, roxas, 
From: ponciano, you can visit: 
	ponciano, san_pedro, claveria, roxas, 
From: talomo, you can visit: 
	talomo, ulas, puan, 
From: ulas, you can visit: 
	ulas, puan, talomo, 
From: puan, you can visit: 
	puan, ulas, talomo, 
From: mintal, you can visit: 
	mintal, makilala, 
From: makilala, you can visit: 
	makilala, mintal, 

The output shows the possible nodes that you can traverse. It is possible to traverse these nodes because these are either the neighbors of the source node or the neighbors of the neighbors of the source nodes (transitive property).

About these ads