無向圖上的DFS？

Question

我正在研究一個由在特定學校是朋友的學生組成的無向友誼圖。我想使用dfs來獲得派系（圖中所有連接的子圖）。但由於某些原因，我的DFS無法正常工作..對算法或代碼的任何建議表示讚賞

這是手動創建一個樣品圖..

import java.util.LinkedHashMap; 


public class DFS { 

    /** 
    * @param args 
    */ 

    class Node { 

     String personName, schoolName; 
     Node next; 

     public Node(String personName, String schoolName, Node next) { 

      this.personName = personName; 
      this.schoolName = schoolName; 
      this.next = next; 
     } 

     public String toString() { 

      return this.personName + " " + this.schoolName; 

     } 

    } 

    public Node[] build() { 

     Node[] graph = new Node[6]; 

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

      Node temp = new Node(Integer.toString(i + 1), "MIT", null); 
      graph[i] = temp; 

     } 

     graph[0].next = new Node("2", "MIT", null); 

     graph[1].next = new Node("1", "MIT", null); 
     graph[1].next.next = new Node("3", "MIT", null); 
     graph[1].next.next.next = new Node("4", "MIT", null); 

     graph[2].next = new Node("2", "MIT", null); 
     graph[2].next.next = new Node("4", "MIT", null); 

     graph[3].next = new Node("3", "MIT", null); 
     graph[3].next.next = new Node("2", "MIT", null);  

     graph[4].next = new Node("6", "MIT", null); 
     graph[5].next = new Node("5", "MIT", null); 

     printGraph(graph); 

     return graph; 

    } 

    public void dfsDriver() { 

     Node[] graph = build(); 

     LinkedHashMap<String, Integer> names = new LinkedHashMap<String, Integer>(); 

     int count = 0; 

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

      if (graph[i] != null) { 

       names.put(graph[i].personName, count); 

       count++; 
      }    
     } 

     boolean[] visited = new boolean[graph.length]; 

     for (int v = 0; v < visited.length; v++) { 

      visited[v] = false; 
     } 


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

      if (graph[i] != null) { 

       if (!visited[i]) { 

         System.out.println("Starting at " + graph[i].personName); 

         dfs(i, visited, names, graph);      
       }    
      }    
     } 

    } 

    private void dfs(int i, boolean[] visited, LinkedHashMap<String, Integer> names, Node[] subGraph) { 

     visited[i] = true; 

     for (Node e = subGraph[i].next; e != null; e = e.next) { 

      System.out.println("visiting " + e.personName); 

      int index = names.get(e.personName); 

      if (!visited[index]) { 

       dfs(index, visited, names, subGraph); 

      }   
     } 

    } 

    public void printGraph(Node[] list) { 

     System.out.println(); 

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

      if (list[i] != null) { 

       System.out.print(list[i]); 

       for (Node a = list[i].next; a != null; a = a.next) { 

        System.out.print(" " + a); 

       } 

       System.out.println(); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     DFS a = new DFS(); 

     a.dfsDriver(); 

    } 

} 

Answer 1

＃1：圖作成是效率低下。 看到這個方法在你的代碼：

public Node[] build() { 

有，你想看看有多少次你叫「new Node」 6個節點。它的6 + 10倍..試圖修改你的數據結構，以便它們適合輸入。 當前DS是：

class Node { 
    String personName, schoolName; 
    Node next; 

想一想修改此，使得每個節點都可以「指向」多個其它節點，而不以其FRENDS每當創建新的對象。

＃2混淆打印語句在DFS方法（）

這應該是這樣的：

private void dfs(int i, boolean[] visited, 
       LinkedHashMap<String, Integer> names, Node[] subGraph) { 
    visited[i] = true; 
    for (Node e = subGraph[i].next; e != null; e = e.next) { 
     int index = names.get(e.personName); 
     if (!visited[index]) { 
      System.out.println("visiting " + e.personName); 
      dfs(index, visited, names, subGraph); 
     }   
    } 
} 

＃3：沒有機制來存儲最終結果

你想從主圖中連接所有的子圖。但是我沒有看到任何規定來存儲/標記圖。您可以修改public void dfsDriver()方法中的第二個for loop方法，以便它可以在每次迭代之後根據訪問的NEW節點創建一個新圖。