在圖中應用訪問者模式來檢測週期

Question

我需要檢測一個有向圖中是否存在一個循環，類似於拓撲排序，但是我想使用訪問者模式..你有一些想法嗎？我可以使用節點的數組列表，以及邊或其他結構（而不​​是數組）。

Answer 1

訪客模式真的無法以最純粹的形式實現這樣的事情。

請記住，訪問者模式通常具有訪問對象網絡的「訪問者」，但「訪問者」指向訪問者。由於訪問者是有效的路徑不知道的，它可以防止某些種類的破壞。

from the wikipedia example of the Visitor pattern (in Java)

class Car implements CarElement { 
    CarElement[] elements; 

    public Car() { 
     //create new Array of elements 
     this.elements = new CarElement[] { new Wheel("front left"), 
      new Wheel("front right"), new Wheel("back left") , 
      new Wheel("back right"), new Body(), new Engine() }; 
    } 

    public void accept(CarElementVisitor visitor) {  
     for(CarElement elem : elements) { 
      elem.accept(visitor); 
     } 
     visitor.visit(this);  
    } 
} 

注意Car accept方法。它確保汽車的所有子元素都被覆蓋，封裝了導航，但卻暴露出對整個數據結構應用外部功能的能力。

由於您的代碼需要瞭解數據結構如何連接在一起，因此訪問者模式很不適合該任務。如果訪問者遇到循環數據結構，未來的訪問者將陷入同一循環，而不是訪問某些的數據，從而破壞了Visitor和VisitAcceptors之間的合約。

現在，如果您在訪問路徑中沒有遵循「可能循環」的鏈接，您可能會稍微達到目標。您仍然必須確保在訪問路徑中遵循圖形的所有節點，只需通過訪問路徑的其他分支。那麼你的訪問者基本上會成爲一大堆節點，這些節點可能會被未經旅行的反向鏈接所擊中，但是當你實施這樣一個奇怪的解決方案時，你會想知道爲什麼你對訪問者部分感到困擾。