Undirected Graph

Some algorithms and code

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;


public class Graph {

    public static void main(String[] args) {

        // Graph instantiate
        UndirectedGraph udGraph = new UndirectedGraph(6);
        udGraph.addEdge(0, 5);
        udGraph.addEdge(2, 4);
        udGraph.addEdge(2, 3);
        udGraph.addEdge(1, 2);
        udGraph.addEdge(0, 1);
        udGraph.addEdge(3, 4);
        udGraph.addEdge(3, 5);
        udGraph.addEdge(0, 2);

        System.out.println(udGraph.toString());

        DFS dfs = new DFS(udGraph, 0);
        DepthFirstPath dfp = new DepthFirstPath(udGraph,0);
        System.out.println("Depth first path");
        for (int w : dfp.pathTo(4)) {
            System.out.print(w + " ");
        }
        System.out.println();

        BreadthFirstPath bfp = new BreadthFirstPath(udGraph, 0);
        System.out.println("Breadth first path");
        for (int w : bfp.pathTo(4)) {
            System.out.print(w + " ");
        }
        System.out.println();

        // connected components
        CC cc = new CC(udGraph);
        System.out.println(" num component is :" + cc.count);


    }
}

// Undirected Graph
class UndirectedGraph {
    public int V;
    public int E;
    public ArrayList<Integer>[] adj;

    public UndirectedGraph(int V) {
        this.V = V;
        adj = (ArrayList<Integer>[]) new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList();
        }    
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];    
    }

    public String toString() {
        String s = V + " vertices, " + E + " edges\n";
        for (int v = 0; v < V; v++) {
            s += v + ": ";
            for (int w : this.adj[v]) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }
}

// Depth first search
class DFS {
    public boolean marked[];
    public int count;

    public DFS(UndirectedGraph G, int s) {
        marked = new boolean[G.V];
        dfs(G, s);
    }

    public void dfs(UndirectedGraph G, int v) {
//        System.out.println("visit " + v);
        marked[v] = true;
        count++;
        for (int w : G.adj(v)) {
            if (!marked[w])
                dfs(G, w);
        }
    }

    public boolean marked(int v) {
        return marked[v];
    }

    public int count() {
        return count;
    }
}

class DepthFirstPath {
    public boolean marked[];
    public int edgeTo[];
    public final int source;

    public DepthFirstPath(UndirectedGraph G, int s) {
        this.source = s;
        marked = new boolean[G.V];
        edgeTo = new int[G.V];
        dfs(G, s);
    }

    public void dfs(UndirectedGraph G, int v) {
        marked[v] = true;
        for (int w : G.adj[v]) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack();
        for (int x = v; x != source; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(source);
        return path;
    }
}

class BreadthFirstPath {
    public boolean marked[];
    public int edgeTo[];
    public final int source;

    public BreadthFirstPath(UndirectedGraph G, int s) {
        this.source = s;
        marked = new boolean[G.V];
        edgeTo = new int[G.V];
        bfs(G, s);
    }

    public void bfs(UndirectedGraph G, int s) {
        LinkedList<Integer> queue = new LinkedList();
        marked[s] = true;
        queue.add(s);
        while(!queue.isEmpty()) {
            int v = queue.pollLast();
            for (int w : G.adj[v]) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.add(w);
                }
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack();
        for (int x = v; x != source; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(source);
        return path;
    }
}

// Depth-first search to find connected components in a graph
class CC {

    public boolean[] marked;
    // divide all the vertices to different groups
    public int[] id;
    public int count;

    public CC(UndirectedGraph G) {
          marked = new boolean[G.V];
          id = new int[G.V];
          for (int s = 0; s < G.V; s++) {
              if (!marked[s]) {
                  dfs(G, s);
                  count++;
              }
          }
    }

     private void dfs(UndirectedGraph G, int v) {
         marked[v] = true;
         id[v] = count;
         for (int w : G.adj[v]) {
             if (!marked[w])
                 dfs(G, w);
         }
     }

     public boolean connected(int v, int w) {
         return id[v] == id[w];  
     }

     public int id(int v) {
         return id[v];  
     }

     public int count() {
         return count;  
     }
}


// Cycle
class Cycle {
    public boolean marked[];
    private boolean hasCycle;
    public int count;

    public Cycle(UndirectedGraph G) {
        marked = new boolean[G.V];
        for (int s = 0; s < G.V; s++) {
            if (!marked[s])
                dfs(G, s, s);    
        }

    }

    public void dfs(UndirectedGraph G, int v, int u) {
        marked[v] = true;
        count++;
        for (int w : G.adj(v)) {
            if (!marked[w])
                dfs(G, w, v);
            else if( w != u) {
                hasCycle = true;
            }
        }
    }

    public boolean marked(int v) {
        return marked[v];
    }

    public int count() {
        return count;
    }
}

class TwoColor {
    public boolean[] marked;
    public boolean[] color;
    private boolean isTwoColorable = true;

    public TwoColor(UndirectedGraph G) {
        marked = new boolean[G.V];
        color = new boolean[G.V];
        for (int s = 0; s < G.V; s++) {
            if (!marked[s])
                dfs(G, s);    
        }
    }

    void dfs(UndirectedGraph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                color[w] = !color[v];
                dfs(G, w);
            } else if (color[w] == color[v]) {
                isTwoColorable = false;    
            }
        }

    }
}