如何对连接对列表进行分组

Question

我有一个从 X 到 Y 的连接列表如下：-

public class Connection
{
    private int X { get; set; }
    private int Y { get; set; }

    public Connection(int X, int Y)
    {
        this.X = X;
        this.Y = Y;
    }
}


List<Connection> connectionList = new List<Connection>();

connectionList.Add(new Connection(1, 2));
connectionList.Add(new Connection(1, 3));
connectionList.Add(new Connection(1, 4));
connectionList.Add(new Connection(2, 1));
connectionList.Add(new Connection(2, 3));
connectionList.Add(new Connection(2, 4));
connectionList.Add(new Connection(3, 1));
connectionList.Add(new Connection(3, 2));
connectionList.Add(new Connection(4, 1));
connectionList.Add(new Connection(4, 2));
connectionList.Add(new Connection(5, 6));

我现在想从 connectionList 中知道我有哪些 groups。例如，这里有两个连接的图表，表示上面的数据。

程序的预期输出将是两组，A(1, 2, 3 4) 和 B(5, 6)。

最好的方法是什么？

Answer 1

这个怎么样;

var groups = new List<List<int>>();
foreach (var con in connectionList)
{
    if(!groups.Any(g => g.Contains(con.X) || g.Contains(con.Y)))
    {
        groups.Add(new List<int>() { con.X, con.Y }); //con.X is not part of any group, so we can create a new one with X and Y added, since both a are in the group       
    } 
    else 
    {
        var group = groups.First(g => g.Contains(con.X) || g.Contains(con.Y));
        if(!group.Contains(con.X)) group.Add(con.X);
        if(!group.Contains(con.Y)) group.Add(con.Y);
    }
}

这是我凭空想到的，也没有测试。目的很简单；

如果任何组中都不存在 X 和 Y，请添加一个新组。
如果 X 或 Y 存在于一个组中，则 Y 或 X 也应该是组的一部分，因此将其添加。

鉴于你的情况，这应该给你两个列表；一个是 (1,2,3,4)，一个是 (5,6)。

编辑：单击 here 查看结果。

Answer 2

您需要找到图中所有断开连接的子图。你需要做的是从一个特定的节点开始，通过实现 DFS or BFS 来遍历连接到你开始的节点的所有节点，并将所有这些节点标记为已访问。当没有更多连接节点时，检查是否有任何非市场节点。如果有任何从特定的未标记节点开始并执行相同的操作，直到没有未标记的节点为止。您还可以查看 Ktuskal 算法 here。该算法稍微复杂一些，因为它描述了断开连接的加权图中的所有三元组。

Answer 3

已接受的答案适用于数据集，但不适用于不同的顺序，例如：

connectionList.Add(new Connection(1, 2));
connectionList.Add(new Connection(3, 4));
connectionList.Add(new Connection(1, 3));

有很多选择可以解决这个问题，但其中之一是：

var groups = new List<List<int>>();
foreach (var con in connectionList)
{
    if(!groups.Any(g => g.Contains(con.X) || g.Contains(con.Y)))
    {
        groups.Add(new List<int>() { con.X, con.Y }); //con.X is not part of any group, so we can create a new one with X and Y added, since both a are in the group       
    } 
    else 
    {
        if(groups.Where(g => g.Contains(con.X) || g.Contains(con.Y)).Count()==1)
        {
           var group = groups.First(g => g.Contains(con.X) || g.Contains(con.Y));
           if(!group.Contains(con.X)) group.Add(con.X);
           if(!group.Contains(con.Y)) group.Add(con.Y);
        }
        if(groups.Where(g => g.Contains(con.X) || g.Contains(con.Y)).Count()>1)
        {
          List<int> groupUnion= new List<int>();
          foreach(var grp in groups.Where(g => g.Contains(con.X) || g.Contains(con.Y)).ToList())
          {
            groupUnion= groupUnion.Union(grp).ToList(); 
            groups.Remove(grp);
          }
          if(!groupUnion.Contains(con.X)) groupUnion.Add(con.X);
          if(!groupUnion.Contains(con.Y)) groupUnion.Add(con.Y);              
          groups.Add(groupUnion);
        }


    }
}

here是代码的例子运行

如何对连接对列表进行分组

How to group a list of connected pairs

c#

graph-theory

edges

nodes