确定等价类的算法

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

解决此问题的一种方法是使用无向图G =(V,E).输入中的每一对代表E中的边,您想要的输出是G 的连接组件.有一些很棒的Python图模块,如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