동급 클래스를 결정하기위한 알고리즘

Question

일반적으로 일반적인 질문입니다. 다음과 같은 목록이 있습니다 :

A B 
A C 
C A 
D E 
F G 
E F 
C L 
M N 

등등.

내가 원하는 것은 - 모든 관계를 파악하고 관련있는 모든 것을 한 줄에 넣는 것입니다. 위의 예는 될 것입니다 :

A B C L 
D E F G 
M N  

모든 문자가 한 번만 표시, 서로 관련 문자 (무엇이든, 목록, 배열) 한 줄에되도록.

잘 정의 된 알고리즘에서 알려진 문제입니까? 이름이 있습니까? 그것이 있어야하는 것처럼 들린다. 나는 일종의 재귀 적 해결책이 있어야한다고 생각한다.

Answer 1

방법 중 하나는 무향 그래프 (undirected graph) G = (V, E)를 사용하는 것이다. 입력의 각 쌍은 E의 모서리를 나타내며, 원하는 출력은 connected components G입니다. NetworkX과 같은 훌륭한 파이썬 그래프 모듈이 있습니다.

데모

>>> data 
[['A', 'B'], ['A', 'C'], ['C', 'A'], ['D', 'E'], ['F', 'G'], ['E', 'F'], ['C', 'L'], ['M', 'N']] 
>>> import networkx as nx 
>>> G = nx.Graph() 
>>> G.add_edges_from(data) 
>>> components = nx.connected_components(G) 
>>> print "\n".join([ " ".join(sorted(cc)) for cc in components ]) 
A B C L 
D E F G 
M N 

Answer 2

https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

(당신이 가장자리의 목록을 가지고 있기 때문에 그들은 당신이하지 않는 가정 반면 있지만, 그들의 제안 된 알고리즘에 대해 너무 많이 걱정하지 마십시오.)

의 편지 노드 부르 자 , 노드 세트는 Component입니다. 모서리 목록이있는 구성 요소 세트를 생성해야합니다. 성분

먼저지도 노드 : 다음

Map<Node, Component> map. 

:이 문제를 해결하기

For each edge E: 
    For each node N in E (i.e. all two of them): 
     Component c = map.get (N) 
     if c doesn't exist then: 
      c = new Component 
      map.put (N, c) 

     c.add (N) 

For each Component C in map.values(): 
    Print (sort C's nodes)