Depth first search of an adjacency list java

Question

I need some help with the DFS function below, while the algorithm for it is an iterative one, I can not figure out how to implement it in my code.

package graphexample;

import java.util.*;
class GraphExample {

class Edge {
  int v, w;
  public Edge(int v, int w){
      this.v = v;
      this.w =w;
  }
  @Override
  public String toString(){
      return "("+v+","+w+")";
  }
}
List<Edge> G[];
boolean marked [];
public GraphExample(int n){
G = new LinkedList[n];
marked = new boolean [n];
Arrays.fill(marked, false);
    for (int i = 0; i < G.length; i++) {
        G[i]=new LinkedList<Edge>();
    }
}
    @Override
    public String toString(){
    String result = "";
    for (int i = 0; i < G.length; i++) 
        result+=i+"=>"+G[i]+"\n";
        return result;
}
    boolean isConnected (int u, int v){
        for (Edge i:G[u])
            if(i.w==v) return true;
        return false;
    }
     /* @param args the command line arguments
     */
    void addEdge(int u, int v, int w){
        G[u].add(0,new Edge(v,w));
    }

Below is the function, which I am stuck on. I know I need to set it up in a way, which I can call dfs() again. As it is, it finds some of the connected edges when I increment v also, but it misses edge 3,1 and 4,0 which are edges with initial node having a higher index than the one it is mapped to. void dfs(int v){

        for (int i = 0; i < G.length; i++) {

            if(isConnected(i,v))
            marked[i]=true;

            //System.out.println("i:"+i+"v:"+v);
        }
        for (int i = 0; i < G.length; i++) {
            if(marked[i]==true)
            System.out.println("Here is a connected node"+G[i]);
        }

    }

    public static void main(String[] args) {
        GraphExample g = new GraphExample(5);
        g.addEdge(0,0,1);
        g.addEdge(1, 1, 3);
        g.addEdge(3, 3, 1);
        g.addEdge(1, 1, 2);
        g.addEdge(2, 2, 4);
        g.addEdge(4, 4, 0);
        System.out.println(g);
        System.out.println("Is node 2 connected to node 4?"+g.isConnected(4, 0));
        g.dfs(0);
    }

}

Thank you for your help. Below I have posted the updated code with Depth and Breadth First Modules. I would appreciate some feedback on whether the BFS section is correct, and if there is a better way of accomplishing the task. Note: this is not an assignment of any sort.

package graphexample;

import java.util.*;
class GraphExample {

class Edge {
  int v, w;
  public Edge(int v, int w){
      this.v = v;
      this.w =w;
  }
  @Override
  public String toString(){
      return "("+v+","+w+")";
  }
}
List<Edge> G[];
//boolean marked [];
public GraphExample(int n){
G = new LinkedList[n];
//marked = new boolean [n];
//Arrays.fill(marked, false);
    for (int i = 0; i < G.length; i++) {
        G[i]=new LinkedList<Edge>();
    }
}
    @Override
    public String toString(){
    String result = "";
    for (int i = 0; i < G.length; i++) 
        result+=i+"=>"+G[i]+"\n";
        return result;
}
    boolean isConnected (int u, int v){
        for (Edge i:G[u])
            if(i.w==v) return true;
        return false;
    }
    int getVertex (GraphExample G[], int v){
    int i;
    return 0;
    }
     /* @param args the command line arguments
     */
    void addEdge(int u, int v, int w){
        G[u].add(0,new Edge(v,w));
    }
    void DFSUtil(int v, boolean [] visited) {

    visited[v] = true;
    System.out.println("DFS: Just visited"+v+" ");


    Iterator<Edge> i = G[v].listIterator();
    while (i.hasNext())
    {
        int n = i.next().w;
        if (!visited[n])
            DFSUtil(n, visited);
    }
}
    void dfs(int v){
    boolean visited[]; 
    visited = new boolean[G.length];
    // Call the recursive helper function to print DFS traversal
    DFSUtil(v, visited);
    }
    void bfs(int v){
        boolean visited[];
        visited = new boolean[G.length];
        visited[v]=true;
        Queue q = new LinkedList();
        for (int i = 0; i < G.length; i++) {
            q.add(i);

        }
        //System.out.println("Here is what is in the Queue"+q);     
        while (!q.isEmpty()) {
            int s = (int)q.poll();//I am not sure if casting is a ok or if there
            //is a better way 
            //System.out.println("This is from Queue during BFS:"+s);
            Iterator<Edge> It = G[s].listIterator();
            while(It.hasNext()){
                Edge n = It.next();
                if (!visited[n.w]){
                    visited[n.w]=true;
                    q.add(n.w);
                    System.out.println("BFS: Just visited"+n.w);}
            }
        }
    }
    public static void main(String[] args) {
        GraphExample g = new GraphExample(5);
        g.addEdge(0,0,1);
        g.addEdge(1, 1, 3);
        g.addEdge(3, 3, 1);
        g.addEdge(1, 1, 2);
        g.addEdge(2, 2, 4);
        g.addEdge(4, 4, 0);
        System.out.println(g);
        System.out.println("Is node 2 connected to node 4?"+g.isConnected(4, 0));
        g.dfs(0);
        g.bfs(0);
    }

}

Answer 1

void DFSUtil(int v,boolean visited[])
{

    visited[v] = true;
    System.out.print(v+" ");


    Iterator<Integer> i = adj[v].listIterator();
    while (i.hasNext())
    {
        int n = i.next();
        if (!visited[n])
            DFSUtil(n, visited);
    }
}


void DFS(int v)
{

    boolean visited[] = new boolean[V];

    // Call the recursive helper function to print DFS traversal
    DFSUtil(v, visited);
}