爲文件中的整數實現強連接組件

我正在從數字輸入文件實現強連接組件程序。我知道如何做到這一點，但很難在python中實現它的算法。爲文件中的整數實現強連接組件

強連接組分（G） 1. G上運行DFS來計算結束時間 2.計算G「 3.運行DFS上G」，但選擇訪問次數哪個節點爲了這樣做時減小結束時間 4.輸出的每個樹的深度優先森林的頂點（如在步驟1計算的）的步驟3中作爲一個單獨的強連通分量的

文件看起來像這樣：

第一行是no。其餘的線是由空間分隔的兩個整數u和v，這意味着從節點u到節點v的有向邊。輸出將是強連通分量和這些分量的數量。

DFS(G) 
1 for each vertex u in G.V 
2  u.color = WHITE 
3  u.π = NIL 
4 time = 0 
5 for each vertex u in G.V 
6  if u.color == WHITE 
7   DFS-VISIT(G, u) 

DFS-VISIT(G, u) 
1 time = time + 1 // white vertex u has just been discovered 
2 u.d = time 
3 u.color = GRAY 
4 for each v in G.adj[u] 
5  if v.color == WHITE 
6   v.π = u 
7   DFS-VISIT(G, u) 
8 u.color = BLACK // blacken u; it is finished 
9 time = time + 1 
10 u.f = time

在上述算法中，我應該如何遍歷反向圖來找到SCC。

來源

2014-10-09 Rgeek

這裏用Python實現。

請注意，我構造G和G'在同一時間。我的DFS也進行了修改。 visited數組存儲每個節點在哪個組件中。此外，DFS還會收到sequence參數，即節點將被測試的順序。在第一個DFS中，我們傳遞了一個xrange（n），但在第二次，我們傳遞了第一次執行中的反轉（順序）。

程序將輸出類似：

3 
[1, 1, 1, 2, 3]

在該輸出中，我們有3個強連通分量，以在單個部件中每個3個第一節點和剩下的兩個與一個組件。

def DFSvisit(G, v, visited, order, component): 
    visited[v] = component 
    for w in G[v]: 
     if not visited[w]: 
      DFSvisit(G, w, visited, order, component) 
    order.append(v); 

def DFS(G, sequence, visited, order): 
    components = 0 
    for v in sequence: 
     if not visited[v]: 
      components += 1 
      DFSvisit(G, v, visited, order, components) 

n, m = (int(i) for i in raw_input().strip().split()) 

G = [[] for i in xrange(n)] 
Gt = [[] for i in xrange(n)] 
for i in xrange(m): 
    a, b = (int(i) for i in raw_input().strip().split()) 
    G[a-1].append(b-1) 
    Gt[b-1].append(a-1) 

order = [] 
components = [0]*n 

DFS(G, xrange(n), [0]*n, order) 
DFS(Gt, reversed(order), components, []) 

print max(components) 
print components

來源

2014-10-09 16:00:37

能否請您解釋代碼如果可能的話？你如何利用從file.Did您使用此輸入 - 開放（文件名）爲行： – Rgeek 2014-10-09 16:13:20

我假設你正在閱讀stdin，就像在大多數比賽中所做的那樣。您不必打開文件，只需使用'python source.py 2014-10-09 16:17:13

好吧，我瞭解您定義的遞歸函數，但不能在此之後。 – Rgeek 2014-10-09 16:32:11

-1

class graphSCC: 
    def __init__(self, graplist): 
     self.graphlist = graphlist 
     self.visitedNode = {} 
     self.SCC_dict = {}  
     self.reversegraph = {} 

def reversegraph(self): 
    for edge in self.graphlist: 
     line = edge.split("\t") 
     self.reverseGraph.setdefault(strip("\r"), []).append() 
    return self.reverseGraph 

def dfs(self): 
    SCC_count = 0 
    for x in self.reversegraph.keys(): 
     self.visitednode[x] = 0 

    for x in self.reversegraph.keys(): 
     if self.visitednode[x] == 0: 
      count += 1 
      self.explore(x, count) 

def explore(self, node, count): 
    self.visitednode[node] = 1 

    for val in self.reversegraph[node]: 
     if self.visitednode[val] == 0: 
      self.explore(val, count) 
    self.SCC_dict.setdefault(count, []).append(node) 

length = 0 
node = 0 
for x in graph.SCC_dict.keys(): 
    if length < len(graph.SCC_dict[x]): 
     length = len(graph.SCC_dict[x]) 
     node = x

長度所需答案

來源

2015-04-16 00:34:24 Noob

請解釋這段代碼如何工作以及爲什麼工作。 – hexafraction 2015-04-16 00:48:00

爲文件中的整數實現強連接組件

回答

相關問題