這個Tarjan算法的實現有什麼問題？

我已經實現了Tarjan的算法，遵循Wikipedia's article，但是我遇到了一個問題。我試圖做的是找到大小大於1的所有強連通組件。對於較小尺寸的輸入，一切正常，但是，當使用input.txt進行測試時，該算法開始出現奇怪的行爲 - 更改初始值n（用於例1，-10，3）程序給出了不同的結果。這就是我無法理解的。該算法不應該依賴於初始值，因爲n僅用作時間戳。如果有任何想法，請分享它，這將非常有幫助，謝謝。這個Tarjan算法的實現有什麼問題？

下面的代碼：

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.HashSet; 
import java.util.Stack; 

public class GraphAlgorithms { 
    HashMap<String, HashSet<String>> graph; 
    int n; 

    public GraphAlgorithms(String fileName) { 
     graph = new HashMap<String, HashSet<String>>(); 
     try (BufferedReader reader = new BufferedReader(new FileReader(fileName))) { 
      String line; 
      while ((line = reader.readLine()) != null) { 
       String[] tokens = line.split(" +"); 
       HashSet<String> to = new HashSet<String>(); 
       for (int i = 1; i < tokens.length; i++) 
        to.add(tokens[i]); 
       graph.put(tokens[0], to); 
      } 
     } catch (IOException e) { 
      e.printStackTrace(); 
     } 
    } 

    public GraphAlgorithms(HashMap<String, HashSet<String>> graph) { 
     this.graph = graph; 
    } 

    private void strongConnect(String v, HashMap<String, Integer> index, 
        HashMap<String, Integer> lowlink, Stack<String> stack, 
        HashSet<String> inStack, ArrayList<HashSet<String>> ans) 
    { 

     index.put(v, n); 
     lowlink.put(v, n); 
     ++n; 
     stack.push(v); 
     inStack.add(v); 

     HashSet<String> successors = graph.get(v); 

     for(String w : successors) { 
      if (!index.containsKey(w)) { 
       strongConnect(w, index, lowlink, stack, inStack, ans); 
       if (lowlink.get(w) < lowlink.get(v)) 
        lowlink.put(v, lowlink.get(w)); 
      } 
      else if (inStack.contains(w)) { 
       if (index.get(w) < lowlink.get(v)) 
        lowlink.put(v, index.get(w)); 
      } 
     } 

     if (index.get(v) == lowlink.get(v)) { 
      HashSet<String> connectedComponent = new HashSet<String>(); 
      String w; 
      do { 
       w = stack.pop(); 
       inStack.remove(w); 
       connectedComponent.add(w); 
      } 
      while (!w.equals(v)); 

      ans.add(connectedComponent); 
     } 
    } 

    public ArrayList<HashSet<String>> getStronglyConnectedComponents() { 
     HashMap<String, Integer> index = new HashMap<String, Integer>(); 
     HashMap<String, Integer> lowlink = new HashMap<String, Integer>(); 
     Stack <String> stack = new Stack<String>(); 
     HashSet<String> inStack = new HashSet<String>(); 
     ArrayList<HashSet<String>> ans = new ArrayList<HashSet<String>>(); 

     n = 0; 
     for (String v : graph.keySet()) { 
      if (!index.containsKey(v)) 
       strongConnect(v, index, lowlink, stack, inStack, ans); 
     } 

     return ans; 
    } 

    public void printComponentsLargerThanOne() { 
     for (HashSet<String> component : getStronglyConnectedComponents()) { 
      if (component.size() > 1) { 
       for (String element : component) { 
        System.out.print(element + " "); 
       } 
       System.out.println(); 
      } 
     } 
    } 
}

和主類

public class Main { 
    public static void main(String[] args) { 
     GraphAlgorithms ga = new GraphAlgorithms("input.txt"); 
     ga.printComponentsLargerThanOne(); 
    } 
}

來源

2013-08-25 svs

由於Java顯然不java.lang.Integer類型，該行的並不總是實習生對象

if (index.get(v) == lowlink.get(v)) {

應

if (index.get(v).equals(lowlink.get(v))) {

來源

2013-08-25 12:46:43

這個Tarjan算法的實現有什麼問題？

回答

相關問題