Первый поиск в глубине списка смежности Java

Question

Мне нужна некоторая помощь с функцией DFS ниже, хотя алгоритм для нее итеративный, я не могу понять, как реализовать ее в своем коде.

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));
    }

Ниже приведена функция, на которой я застрял. Я знаю, что мне нужно настроить его так, чтобы я мог снова вызвать dfs(). Как таковой, он находит некоторые из связанных ребер, когда я также увеличиваю v, но он пропускает ребра 3,1 и 4,0, которые являются ребрами с начальным узлом, имеющим более высокий индекс, чем тот, которому он сопоставлен. 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);
    }

}

Спасибо за помощь. Ниже я разместил обновленный код с модулями глубины и ширины. Буду признателен за некоторые отзывы о том, является ли раздел BFS правильным, и есть ли лучший способ выполнить задачу. Примечание: это не какое-либо задание.

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);
}