Graph

Graph related questions mainly focus on depth first search and breath first search. Depth first search is straightforward, you can just loop through neighbors starting from the root node.

Below is a simple implementation of a graph and breath first search. The key is using a queue to store nodes.

breath-first-search

1) Define a GraphNode

class GraphNode{ 
	int val;
	GraphNode next;
	GraphNode[] neighbors;
	boolean visited;
 
	GraphNode(int x) {
		val = x;
	}
 
	GraphNode(int x, GraphNode[] n){
		val = x;
		neighbors = n;
	}
 
	public String toString(){
		return "value: "+ this.val; 
	}
}

2) Define a Queue

class Queue{
	GraphNode first, last;
 
	public void enqueue(GraphNode n){
		if(first == null){
			first = n;
			last = first;
		}else{
			last.next = n;
			last = n;
		}
	}
 
	public GraphNode dequeue(){
		if(first == null){
			return null;
		}else{
			GraphNode temp = new GraphNode(first.val, first.neighbors);
			first = first.next;
			return temp;
		}	
	}
}

3) Breath First Search uses a Queue

public class GraphTest {
 
	public static void main(String[] args) {
		GraphNode n1 = new GraphNode(1); 
		GraphNode n2 = new GraphNode(2); 
		GraphNode n3 = new GraphNode(3); 
		GraphNode n4 = new GraphNode(4); 
		GraphNode n5 = new GraphNode(5); 
 
		n1.neighbors = new GraphNode[]{n2,n3,n5};
		n2.neighbors = new GraphNode[]{n1,n4};
		n3.neighbors = new GraphNode[]{n1,n4,n5};
		n4.neighbors = new GraphNode[]{n2,n3,n5};
		n5.neighbors = new GraphNode[]{n1,n3,n4};
 
		breathFirstSearch(n1, 5);
	}
 
	public static void breathFirstSearch(GraphNode root, int x){
		if(root.val == x)
			System.out.println("find in root");
 
		Queue queue = new Queue();
		root.visited = true;
		queue.enqueue(root);
 
		while(queue.first != null){
			GraphNode c = (GraphNode) queue.dequeue();
			for(GraphNode n: c.neighbors){
 
				if(!n.visited){
					System.out.print(n + " ");
					n.visited = true;
					if(n.val == x)
						System.out.println("Find "+n);
					queue.enqueue(n);
				}
			}
		}
	}
}

Output:

value: 2 value: 3 value: 5 Find value: 5
value: 4
import java.util.LinkedList;

public class Graph {

    private int V;                         // number of vertices
    private int E;                         // number of edges
    private LinkedList[] adjlist; // adjecency lists

// creates a graph with V vertices and 0 edges

    @SuppressWarnings("unchecked")
    public Graph(int V) {
        this.V = V;
        adjlist = (LinkedList[])new LinkedList[V];
        for (int v = 0; v < V; v++) {
            adjlist[v] = new LinkedList();
        }
    }

// returns the number of vertices in this graph
    public int V() {
        return V;
    }

// returns the number of edges in this graph
    public int E() {
        return E;
    }

// adds an edge to this graph
    public void addEdge(int v, int w) {
        adjlist[v].add(w);
        adjlist[w].add(v);
        E++;
    }


// returns the list of vertices adjacency to v

    public Iterable adj(int v) {
        return adjlist[v];
    }


// does this graph contain the edge (v,w)?
    public boolean containsEdge(int v, int w) {
        return adjlist[v].contains(w);
    }


// adds a new vertex into the graph without any edges
    public void addVertex() {
        V++;
    }


// returns the adjacency matrix for this graph

    public boolean[][] adjMatrix() {
        boolean[][] result = new boolean [V][V];
        for(int i=0; i<V; i++) {
            for (int j=0; j<V; j++) result[i][j] = false;
            for (int j = 0; j < adjlist[i].size(); j++)
                result[i][(Integer) adjlist[i].get(j)] = true;
        }
        return result;
    }


// returns true if and only if the graph contains a three cycle (triangle)

    public boolean containsTriangle() {
        //check all edges, and not all vertices pairs - with another vertex that forms a triangle -
        // it is enough information to determine if the edge and vertex form a feasible solution.
        boolean[][] temp = adjMatrix();
        for (int i = 1; i<V; i++)
            for (int j= i+1; j<V; j++)
                if (temp[i][j]==true) //have edges
                    for (int k=0; k<V; k++)
                        if (temp[k][i] && temp[k][j]) return true;

        return false;
    }


// returns true if and only if the graph contains a cycle (of arbitrary length)

    public boolean containsCycle() {
        if (V==0) return false;
        boolean[] result = new boolean[V];
        for (int i=0; i<V; i++) result[i] = false;
        int root = 0;
        LinkedList  set = new LinkedList ();
        set.add(1);
        result[1] = true;
        while (set.size()>0){
            int tem = set.poll();
            for (int j=0; j< adjlist[tem].size(); j++) {
                int tem2 = (Integer) adjlist[tem].get(j);
                if (result[tem2]) return true;
                else {
                    set.add(tem2);
                    result[tem2] = true;
                }
            }
        }
        return false;
    }


// returns true if and only if the graph is bipartite

// equivalently, returns true if and only if the graph contains an odd-length cycle

 public boolean isBipartite() {
        if (V<=0) return false;
        int colorArr[] = new int[V];
        int src = 0;
        boolean[][] G = adjMatrix();
        for (int i=0; i<V; ++i)
            colorArr[i] = -1;

        // Assign first color to source
        colorArr[src] = 1;

        // Create a queue (FIFO) of vertex numbers and enqueue
        // source vertex for BFS traversal
        LinkedListq = new LinkedList();
        q.add(src);

        // Run while there are vertices in queue (Similar to BFS)
        while (q.size() != 0)
        {
            // Dequeue a vertex from queue
            int u = q.poll();
            // Find all non-colored adjacent vertices
            for (int v=0; v<V; ++v)
            {
                // An edge from u to v exists and destination v is
                // not colored
                if (G[u][v] && colorArr[v]==-1)
                {
                    // Assign alternate color to this adjacent v of u
                    colorArr[v] = 1-colorArr[u];
                    q.add(v);
                }

                // An edge from u to v exists and destination v is
                // colored with same color as u
                else if (G[u][v] && colorArr[v]==colorArr[u])
                    return false;
            }
        }
        // If we reach here, then all adjacent vertices can
        //  be colored with alternate color
        return true;
    }
}