C# 根据友谊将一些元素重新分组到不同的组中而没有循环

Question

我正在努力解决一个问题，即根据他们的友谊将一些元素分组到不同的组中。

例如，

输入:

 R1: R2, R6, R8, R10   // all elements in one group are friends
 R6: R1, R7, R8, R12 
 R8: R2, R5, R6, R10 
 R4: R11, R15, R16, R13  // **UPDATE** this is a group that do not have overlap with all other groups 

对于R1来说，所有R1的 friend 的 friend 也是R1的 friend ，需要归到同一组等等。

预期输出:

 R1: R2, R6, R8, R10 , R7, R5, R12
 R4: R11, R15, R16, R13   // **UPDATE**

输出可能是两组或更多组。这取决于输入。

现在，数据存储在 Visual Studio 2012 中的 C# 字典中。

我发现分组过程中可能存在循环

示例，R1 ---> R6 ---> R8 --> R6

你能帮我找到解决循环问题的方法吗？

如有任何帮助，我们将不胜感激。

谢谢

Answer 1

演示代码如下:

    private static Dictionary<string, List<string>> ProcessData(Dictionary<string, List<string>> data)
    {
        var processedData = new Dictionary<string, List<string>>();
        var masterList = new List<string>();
        foreach (var value in data.Keys)
        {
            if (!masterList.Contains(value))
            {
                var friendList = FindFriends(data, value);
                masterList.AddRange(friendList);
                processedData.Add(value, friendList);
            }
        }
        return processedData;
    }

    private static List<string> FindFriends(Dictionary<string, List<string>> data,string source)
    {
        var friendMasterList = new List<string>();
        var friendQueue = new Queue<string>();
        if (data.ContainsKey(source))
        { 
            foreach (var value in data[source])
            {
                friendQueue.Enqueue(value);
            }
            while (friendQueue.Count > 0)
            {
                var value = friendQueue.Dequeue();
                if (!friendMasterList.Contains(value))
                    friendMasterList.Add(value);

                if (data.ContainsKey(value))
                {
                    foreach (var value2 in data[value])
                    {
                        if (!friendMasterList.Contains(value2))
                            friendQueue.Enqueue(value2);
                    }
                }
            } 
        }
        if (friendMasterList.Contains(source))
            friendMasterList.Remove(source);
        return friendMasterList;
    }