邻接表的深度优先搜索 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);
}

邻接表的深度优先搜索 java

Depth first search of an adjacency list java

java

microsoft-distributed-file-system