用于确定等同类别的算法

而是一般问题。我有这样一个列表：用于确定等同类别的算法

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

让每个字母只出现一次，而且相互关联的字母都在一行上（列表，数组，等等）。

这是一种已知的问题，具有明确的算法？它有名字吗？听起来应该是这样。我会假设某种递归解决方案应该到位。

来源

2014-03-07 ozhogin

关闭选民：这是关于图（寻找连接组件）OP只是不知道名字完全明确的问题。它不是“太宽泛”。 – senshin

从[等价关系]（http://en.wikipedia.org/wiki/Equivalence_relation）中正式说出您正在寻找的是[等同类]（http://en.wikipedia.org/wiki/Equivalence_class）。这是一个公平的问题。 – ArtB

的一种方式是使用一个无向图G =（V，E）。输入中的每一对代表E中的一条边，并且所需的输出是G的connected components。有一些很棒的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

来源

2014-03-07 15:03:56 mdml

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

（但不要太担心自己的建议的算法，因为你有边缘的名单，而他们认为你不知道。）

我们来电来函节点，以及一组节点。您需要生成一组给定边缘列表的组件。

首先，地图节点到组件：

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)

来源

2014-03-07 15:03:33 user3392484

用于确定等同类别的算法

回答

相关问题