來自最少節點數的弱連接圖遍歷

Question

我已經給出了以下練習：有一個未加權的，定向的，弱連接的圖，其中有n個節點（n < 1 000 000）。我們想要遍歷整個圖，從最少的節點開始。問題是：我從哪個節點開始遍歷？我無法在這個特定主題上找到任何內容。不過，我設法拿出一個算法，但它不是足夠有效的：

• 我該圖存儲在鄰接表（n可以是太高了一個二維矩陣）
• 我開始BFS從每個節點i，並將其存儲在x[i][...]（x = List<List<int>>）
• 達到節點我檢查我是否有x[i].Count == n
• 檢查是否有(x[i] union x[j]).Count == n
• 我檢查是否任何(x[i] union x[j] union x[k]).Count == n ...所以我做所有可能的2，3，4 ... x的子集合，並檢查其計數是否爲n。

它工作正常，如果n不是太高，但我會需要一個更有效的算法更大的n。

任何幫助表示讚賞（你會讓我能夠再次入睡）！ :)

Answer 1

查找沒有任何傳入邊緣的節點。遍歷這些節點，並且對於每個節點v，開始遍歷圖。記住你訪問過哪些節點（通過將它們放在散列表中或標記它們）。當你到達你已經訪問過的節點時停止遍歷。

您需要一個鄰接列表表示法，其中每個節點都有一個傳入列表和一個傳出邊緣列表。然後做這樣的事情：

Set nodesToVisit = emptySet; 
for i=1 to n: 
    if incoming[i].size() == 0: 
     nodesToVisit.add(i) 

Set visited = emptySet; 
for v in nodesToVisit: 
    nodesToVisit.remove(v) 
    if(v is not in visited): 
     visit(v); 
     visited.add(v); 
     for u in outgoing[v]: 
      nodesToVisit.add(u)