尝试在Java中实现DFS

试图对此Adjacent Graph类实现DFS算法。我无法将sudo代码实现到Java中。我看到一些例子实现了一个int数组来存储访问值，以及其他一些使用布尔数组来存储被访问值的例子。对这些设计选择的优缺点有一些了解。尝试在Java中实现DFS

DFS() 
     count = 0 
     for each vertex v in V do 
      if v is marked with 0 
       dfs(v) 

    dfs(v) 
     count = count +1 
     for each vertex w in V adjacent to v do 
      if w is makred with 0 
       dfs(w) 

    public class AdjGraphDFS 
    { 
     private int  v; 
     private int  counter; 
     private int  [] visited; 
     private boolean [][] adj; 

     public boolean directed; 

     public AdjGraphDFS(int vector) 
     { 
      v = vector; 
      adj = new boolean[ v ][ v ];   
     } 

     public void addEdge(int u, int v) 
     { 
      if(directed == true) 
      { 
       adj[u][v] = true; 
      } 

      else 
      { 
       adj[v][u] = true; 
       adj[u][v] = true; 
      } 
     } 
    // This is where I fail to implement DFS logic correctly 
    public void DFS() 
     { 
      counter = 0; 
      for (int i = 0; i < adj.length; i++) 
      { 
       if(visited[i] == 0) 
       { 
        dfs(v); 
       } 
      }  
     } 

Here is my attempt at implementing the recursive dfs(v) 

     // and this is where I fail to implement dfs(v) correctly 
     public void dfs(int v) 
     {  
      ++counter; 
      for(int i = 0; i < adj.length; i++) 
      {   
       if(/* w is unvisited */) 
       { 
        dfs(v); 
        visited[i] = counter; 
       } 

       System.out.println("Visiting vertex " + v); 
      }

这里

来源

2014-11-08 aguilar

INT与布尔'visited'阵列的一个反面：在int数组需要更多的内存，大约4倍（[预计]（http://stackoverflow.com/questions/383551/what -is-the-size-of-a-boolean-in-java））在Java中具有相似大小的布尔数组。我没有理由使用int数组。 – irrelephant 2014-11-08 05:50:33

很高兴知道。我确实想要实现一个贪婪的算法。谢谢 – aguilar 2014-11-08 23:14:22

你是不是检查w是为V A的邻居。你也需要为递归调用之前访问标记顶点。你的循环应该像

// println("Visiting " + v); 

for(int i = 0; i < adj.length; i++) 
{   
    if(adj[v][i] && (visited[i] == 0)) 
    { 
     visited[i] = counter; 
     dfs(i); 
    } 
}

来源

2014-11-08 05:05:01 mutaflux

非常感谢。只是为了澄清这是我需要在我的dfs（v）方法中实现的逻辑。但是我仍然对DFS（）方法的if条件感到迷茫。 – aguilar 2014-11-08 05:13:22

您不需要DFS（）方法。搜索始终从特定的顶点开始，例如从图的第一个顶点开始： dfs（0） – mutaflux 2014-11-08 05:32:03

尝试在Java中实现DFS

回答

相关问题