Python thành phần kết nối

Question

Tôi đang viết một hàm get_connected_components cho một lớp Graph:

def get_connected_components(self): 
    path=[] 
    for i in self.graph.keys(): 
     q=self.graph[i] 
     while q: 
      print(q) 
      v=q.pop(0) 
      if not v in path: 
       path=path+[v] 
    return path 

đồ thị của tôi là:

{0: [(0, 1), (0, 2), (0, 3)], 1: [], 2: [(2, 1)], 3: [(3, 4), (3, 5)], \ 
4: [(4, 3), (4, 5)], 5: [(5, 3), (5, 4), (5, 7)], 6: [(6, 8)], 7: [], \ 
8: [(8, 9)], 9: []} 

nơi các phím là các nút và các giá trị là các cạnh. chức năng của tôi mang lại cho tôi phần kết nối này:

[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), \ 
(5, 4), (5, 7), (6, 8), (8, 9)] 

Nhưng tôi sẽ có hai thành phần kết nối khác nhau, như:

[[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), \ 
(5, 3), (5, 4), (5, 7)],[(6, 8), (8, 9)]] 

Tôi không hiểu nơi tôi đã sai lầm. Có ai giúp tôi không?

Answer 1

Hãy đơn giản hóa các biểu đồ:

myGraph = {0: [1,2,3], 1: [], 2: [1], 3: [4,5],4: [3,5], 5: [3,4,7], 6: [8], 7: [],8: [9], 9: []} 

Ở đây chúng ta có chức năng quay trở lại một cuốn từ điển có phím là rễ và có giá trị là các thành phần kết nối:

def getRoots(aNeigh): 
    def findRoot(aNode,aRoot): 
     while aNode != aRoot[aNode][0]: 
      aNode = aRoot[aNode][0] 
     return (aNode,aRoot[aNode][1]) 
    myRoot = {} 
    for myNode in aNeigh.keys(): 
     myRoot[myNode] = (myNode,0) 
    for myI in aNeigh: 
     for myJ in aNeigh[myI]: 
      (myRoot_myI,myDepthMyI) = findRoot(myI,myRoot) 
      (myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot) 
      if myRoot_myI != myRoot_myJ: 
       myMin = myRoot_myI 
       myMax = myRoot_myJ 
       if myDepthMyI > myDepthMyJ: 
        myMin = myRoot_myJ 
        myMax = myRoot_myI 
       myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1])) 
       myRoot[myMin] = (myRoot[myMax][0],-1) 
    myToRet = {} 
    for myI in aNeigh: 
     if myRoot[myI][0] == myI: 
      myToRet[myI] = [] 
    for myI in aNeigh: 
     myToRet[findRoot(myI,myRoot)[0]].append(myI) 
    return myToRet 

Hãy thử nó:

print getRoots(myGraph) 

{8: [6, 8, 9], 1: [0, 1, 2, 3, 4, 5, 7]}

Answer 2

Tôi thích thuật toán này:

def connected_components(neighbors): 
    seen = set() 
    def component(node): 
     nodes = set([node]) 
     while nodes: 
      node = nodes.pop() 
      seen.add(node) 
      nodes |= neighbors[node] - seen 
      yield node 
    for node in neighbors: 
     if node not in seen: 
      yield component(node) 

Đây không chỉ là ngắn hạn và thanh lịch, nhưng cũng nhanh. Sử dụng nó như vậy (Python 2.7):

old_graph = { 
    0: [(0, 1), (0, 2), (0, 3)], 
    1: [], 
    2: [(2, 1)], 
    3: [(3, 4), (3, 5)], 
    4: [(4, 3), (4, 5)], 
    5: [(5, 3), (5, 4), (5, 7)], 
    6: [(6, 8)], 
    7: [], 
    8: [(8, 9)], 
    9: []} 

new_graph = {node: set(each for edge in edges for each in edge) 
      for node, edges in old_graph.items()} 
components = [] 
for component in connected_components(new_graph): 
    c = set(component) 
    components.append([edge for edges in old_graph.values() 
          for edge in edges 
          if c.intersection(edge)]) 
print components 

Kết quả là:

[[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), (5, 4), (5, 7)], 
[(6, 8), (8, 9)]]