c# 将连接项的列表排序为多个列表

Question

可以将对象列表分类为多组相互关联的对象吗？

型号:

public class Item
{
   public string Name {get;set;}
   public List<Item> ConnectedItem {get;set;}
}

数据:

    public void Data()
    {
        Item One = new Item() {};
        Item Two = new Item() { };
        Item Three = new Item() { };
        Item Four = new Item() { };
        Item Five = new Item() { };
        Item Six = new Item() { };
        Item Seven = new Item() { };
        Item Eight = new Item() { };
        Item Nine = new Item() { };
        Item Ten = new Item() { };

        One.ConnectedItem = new List<Item>(){Two,Three, Five};
        Two.ConnectedItem = new List<Item>() { One, Five };
        Three.ConnectedItem = new List<Item>() { Five, Two };
        Four.ConnectedItem = new List<Item>() { One, Two };
        Five.ConnectedItem = new List<Item>() { Four, One, Two ,Three };

        Six.ConnectedItem = new List<Item>() { Eight };
        Seven.ConnectedItem = new List<Item>() { Eight };
        Eight.ConnectedItem = new List<Item>() { Six };

        Nine.ConnectedItem = new List<Item>() { Ten };
        Ten.ConnectedItem = new List<Item>() { Nine};

        List<Item> items = new List<Item>(new List<Item>() {One,Two,Three,Four,Five,Six,Seven,Eight,Nine,Ten });


    }

我要归档的是相互关联的项目列表

-收藏1
----一、二、三、四、五

-收藏2
----六、七、八

-收藏3
----九、十

        List<List<Item>> sortedList = new List<List<Item>>()
        {
            new List<Item>() {One, Two,Three,Four,Five},
            new List<Item>() {Six,Seven,Eight},
            new List<Item>() {Nine,Ten},
        };

Answer 1

您要做的是找到您的模型暗示的图的连通分量。连接的组件可以通过执行 DFS 找到从一个节点开始，DFS完成后，继续寻找尚未找到的节点。我假设你有一个数组或列表 L 中的所有项目；我还向 Item 添加了一个 Visited 属性。

现在您有一个有向图(Item1 可能指向 Item2，而 Item2 不指向 Item1)。显然，您正在寻找的是通过删除链接上的方向获得的图形的连通分量。

List<List<Item>> components = new List<List<Item>>();
for (int i = 0; i < L.Count; i++)
{
    if (L.Visited) 
        continue;
    var component = new List<Item>();
    DFS(L[i], component);
    components.Add(component);
}

和方法 DFS:

static void DFS(Item item, List<Item> component)
{
    if (component.Contains(item))
        return;
    component.Add(item);
    item.Visited = true;
    foreach (var i in item.ConnectedItems)
    {
         if (!i.Visited)
             DFS(i, component);
    }
    foreach (var i in L)
    {
        if (!i.Visited && i.ConnectedItems.Contains(item))
            DFS(i);
    }
}