無向グラフ上の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のための新しいオブジェクトを毎回作成することなく、複数の他のノードにこのように、各ノードができ、「ポイント」を変更する方法について考えます。

DFS法ではprint文を混乱＃2（）

それはこのようにする必要があります：

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()メソッド内の2番目のfor loopを変更して、各繰り返しの後に訪れたNEWノードから新しいグラフを作成することができます。