GraphClusters.java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author richard.santana
 */
public class GraphClusters {

	public static void main(String[] args) {
		String[] testValue = Arrays.asList("1100","1110","0110","0001").toArray(new String[]{});
		System.out.println(clusterNumber(testValue));
	}

	static int clusterNumber(String[] zombies){
		if(zombies.length == 0){
			return 0;
		}
		int[] visited = new int[zombies.length];
		Queue<Integer> queue = new LinkedList<>();
		int clusterNumber = 0;
		for(int i = 0; i < zombies.length;i++){
			if(visited[i] == 0){
				clusterNumber++;
				visit(i,queue,visited,zombies);
			}
		}

		return clusterNumber;
	}

	static int visit(int i, Queue<Integer> queue, int[] visited, String[] matrix){
		visited[i] = 1;
		queue.add(i);
		while(!queue.isEmpty()){
			Integer vertex1 = queue.poll();
			int vertex2 = proxFromPosition(matrix, vertex1,0);
			while(vertex2 != -1){
				if(visited[vertex2] == 0){
					visited[vertex2] = 1;
					queue.add(vertex2);
				}
				vertex2 = proxFromPosition(matrix,vertex1,vertex2);
			}
		}
		return 0;
	}

	static int proxFromPosition(final String[] matrix, final Integer poll, final Integer initialPosition) {
		String value = matrix[poll];
		for(int i = initialPosition+1; i < matrix.length;i++){
			if(value.charAt(i) == '1' && i != poll){
				return i;
			}
		}
		return -1;
	}
}