嘗試在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

回答

相關問題