算法有向循環圖遍歷（JavaScript的）

我有一個連接時，定向的，環狀的曲線圖。任務是發現圖中的每個單個節點，而不會陷入無限循環，因爲常規的樹遍歷算法會執行此操作。算法有向循環圖遍歷（JavaScript的）

你可以假設我已經知道，以便在向圖到達所有點開始什麼節點，而每個節點我有將回到它引導到節點的功能。有找到所有節點的已知算法嗎？

主要問題是真的，避免循環，我會喜歡它，如果有辦法做到這一點不保持每一個節點的軌跡，並將其與已經被經過的各個節點的列表進行比較。

如果您需要更多的細節，實際的任務是讓JavaScript中每個命名功能列表，包括其他對象的屬性功能。所以，我想類似下面的，因爲我認爲JS對象的引用對方做了一個樹（當然事實並非如此）：

function __findFunctions(obj){ 
    for (var f in obj){ 
    // for special case of edge with self 
    if (obj === obj[f]){ 
     continue 
    } 
    if (typeof obj[f] === 'function' && 
     obj.hasOwnProperty(f) && 
      // exclude native functions, we only want user-defined ones 
     !(/\[(native\scode|object\sfunction)\]/i).test(obj[f].toString()) && 
      // exclude functions with __ prefix 
     !(/^\s*function\s*__/).test(obj[f].toString()) 
     ){ 
     document.write(f + "<br/>" + obj[f].toString() + "<hr/>"); 
    } 
    //alert(typeof obj[f] + "\n" + obj + "\n" + obj[f] + "\n" + f) 
    __findFunctions(obj[f]); 
    } 
} 
__findFunctions(window);

這段代碼的問題是，它陷在週期。

來源

2010-07-08 ehsanul

請忽略正則表達式，在這個問題的背景下不是太重要。儘管我很想知道是否有更好的方式來告訴用戶定義的功能，而不是本地功能。 – ehsanul 2010-07-08 07:24:12

您將需要維持已經訪問過的節點列表，如果你想避免循環。

E.g.

__findFunctions(obj, visited) as your signature 
at start do an "in array" test for current obj and return if so. 
at start add obj to the visited for subsequent traversals.

來源

2010-07-08 07:23:27

我會喜歡它，如果有辦法做到這一點不保持每一個節點的軌跡，並將其與已經被經過的各個節點的列表進行比較。

它可能不像檢查已經遍歷的節點列表那樣糟糕。你可以，而是給每個節點某種形式的獨特ID：

// psuedo 
id=0; 
for each node 
    node.id = id++;

等

然後你就可以在你遍歷每個節點的ID添加到一個哈希：

var alreadyTraversed = {}; 

// Traversing a node: 
alreadyTraversed[node.id] = true;

而且後來，當你需要檢查其是否已經運行：

if (node.id in alreadyTraversed) // It's already been traversed...

或者說，一個真正的解決方案簡陋，簡單地設置您遍歷每個對象的某些屬性：

node._traversed = true; 

// Later: 
if (someNode._traversed) // already traversed.

來源

2010-07-08 07:25:09 James

你的僞代碼不能運行，因爲'對於每個節點'實際上是我尋找的圖遍歷算法。但是，它給了我一個想法，如果JS允許的話：使用節點對象本身作爲ID而不是整數。我在Ruby中做過這樣的事情，我會在JS中嘗試一下。謝謝！ – ehsanul 2010-07-08 07:31:33

@ehsanul：見我的第二個建議的解決方案:) – James 2010-07-08 07:32:44

衛生署，偉大的想法。它不僅是簡單的，它是正確的解決方案。 Nowww我可以睡覺，知道有一個明智的解決方案讓我醒來。 – ehsanul 2010-07-08 07:37:10

算法有向循環圖遍歷（JavaScript的）

回答

相關問題