breadth first search


See On Github

Data

Source Code



import java.util.Iterator;
import java.util.LinkedList;

public class BFS {
	private Graph graph;
	private LinkedList<LinkedList<vertex>> queue;
	private vertex tempVertex;
	private LinkedList<vertex> templist;
	public BFS(Graph graph) {
		queue = new LinkedList<LinkedList<vertex>>();
		this.graph = graph;
		
	}
	public void traverse(){
		find(null);
	}
	public void find(vertex v){
		templist =(LinkedList<vertex>) graph.getconnectedvertices(0);
		templist.getFirst().setVisited(true);
		System.out.println();
		System.out.println("the vertex "+templist.getFirst().getValue()+" is visited");
		queue.add(templist);
		
		while (!queue.isEmpty()){
		templist = queue.pop();
		if(v !=null){
		if(templist.getFirst().equals(v)){
			System.out.println("match found "+templist.getFirst());
			break;
		}
		}
		for (int i = 0; i < templist.size(); i++) {
			tempVertex = templist.get(i);  // to reduce the overhead of lookups
			if (tempVertex.isVisited() == false){
				System.out.println("setting the node visited to true "+tempVertex.getValue());
				templist.get(i).setVisited(true);
				System.out.println("adding node "+tempVertex.getValue()+" to the queue");
				queue.add(graph.getconnectedvertices(tempVertex));
			}
			
			
		}
		System.out.println("the queue is"+queue);
		System.out.println();
		}
		
	}
	public static void main(String[] args) {
		Graph gp = new Graph(10);
		gp.add(new vertex(6), 0);
		gp.add(new vertex(8), 1);
		gp.add(new vertex(9), 2);
		gp.add(new vertex(10), 3);
		gp.addEdge(0, 1);
		gp.addEdge(1,0);
		gp.addEdge(1,2);   //even though the my graph is directed graph just for a simple example created a symmetric(undirected) graph
		gp.addEdge(2,1);
		gp.addEdge(2,3);
		gp.addEdge(3,2);
		gp.addEdge(3,0);
		gp.addEdge(0,3);
		gp.allVertices().forEach(item -> System.out.println(gp.getconnectedvertices(item)));
		BFS x = new BFS(gp);
		x.traverse();
		}
		
		
	}




import java.util.Arrays;
import java.util.LinkedList;
import java.util.function.Function;

public class Graph {
	private LinkedList<vertex>[] linkedlistGroup;
	private int capacity ;
	private Function<Integer, Boolean> isinvalid= (item) -> (item > capacity || item < 0)  ? true : false;
			LinkedList<vertex> temp;
	
	/**
	 * @param capacity
	 */
	
	@SuppressWarnings("unchecked")
	public Graph(int capacity){
		this.capacity=capacity;
		linkedlistGroup = new LinkedList[capacity];
		for (int i = 0; i < capacity; i++) {
			linkedlistGroup[i] = new LinkedList<vertex>();
			
			
		}
		
		
	}
/**
 * @param v - find the <strong>vertex </strong> using the id of the vertex
 * @return an iterable so that u can wrap it in any collection that implements the iterable interface
 */
public Iterable<vertex> getconnectedvertices(int v){
	if(isinvalid.apply(v)) throw new IndexOutOfBoundsException("the vertex is not present in the graph");
		return linkedlistGroup[v];
		
			
	}
	public LinkedList<vertex> getconnectedvertices(vertex v){
		
		
		Arrays.stream(linkedlistGroup).forEach(item -> {
			
			if(!item.isEmpty())
			{
				
				if(item.getFirst().equals(v)){
					temp = item;
					
				}
			}
			
			
		
		} );
		return temp;
		
	}
	
	public void add(vertex v, int loc){
		
		linkedlistGroup[loc].add(v);

	}
	
	public LinkedList<vertex> allVertices(){

		LinkedList<vertex> v = new LinkedList<vertex>(); 
		Arrays.stream(linkedlistGroup).forEach(item ->{
		if(!item.isEmpty())v.add(item.getFirst());
		});	
		return v;
		
	}
	public void addEdge(int to , int from){
		if(isinvalid.apply(to)) throw new IndexOutOfBoundsException("the vertex is not present in the graph");
		if(isinvalid.apply(to)) throw new IndexOutOfBoundsException("the vertex is not present in the graph");
		linkedlistGroup[to].add(linkedlistGroup[from].getFirst());
		
		
	}
	public vertex getvertex(int vertex){
		return linkedlistGroup[vertex].getFirst();
		
		
	}
	public static void main(String[] args) {
		Graph gf = new Graph(10);
	
	}
	
	

}


public class vertex {
	private int value;
	
	private boolean visited;
	public vertex(int value) {
		this.setValue(value);
		
	}
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public boolean isVisited() {
		return visited;
	}
	public void setVisited(boolean visited) {
		this.visited = visited;
	}
	@Override
	public String toString() {
		return value+"";
		
	}
	public boolean equals(vertex obj) {
		return (getValue() == obj.getValue()) ? true :false;
	}

}