# 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.

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

// creates a graph with V vertices and 0 edges

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

// 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) {
E++;
}

// returns the list of vertices adjacency to v

public Iterable adj(int v) {
}

// does this graph contain the edge (v,w)?
public boolean containsEdge(int v, int 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;
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 {
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

// 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];
}

// 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;
}
}
```