I have a dictionary that contains key as stringID and the list of values that have all its children. For example: parent P1 has childId: A,B,C,D. And child B its child id E, child D has its child id F. So output of parent P1 = A,B,C,D,E,F

    var pcLookUp = new Dictionary<string, List<string>>();
    var list = new List<string>();
    list.Add("A");list.Add("B");list.Add("C");list.Add("D");
    pcLookUp.Add("P1", list);
    
    pcLookUp.Add("B", new List<string>() {"E"} );
    pcLookUp.Add("D", new List<string>() {"F"} );
    
    foreach( var k in pcLookUp)
    {
        Console.Write(k.Key   ": ");
        foreach(var v in k.Value)
        {   
            Console.Write(v   " ");
        }
        Console.WriteLine();
    }

What is the efficient way to solve this problem?

CodePudding user response：

Based on my understanding, it looks like you want to flatten a list of nodes, along with all descendents, into a single list.

A real-world analogy might be sending invitations to a family gathering to your children, telling them to invite their children, and so on then wanting a list of everyone who will attend the gathering. The analogy breaks down because I understand from your question that each node can have only zero or one child nodes. If a given node can have zero to N child nodes, the same idea still applies.

var dict = new Dictionary<string, List<Node>>
{
    { "P1", new List<Node>()
        {
            new Node() { Name = "A" },
            new Node() { Name = "B", Child = new Node() { Name = "E" } },
            new Node() { Name = "C" },
            new Node() { Name = "D", Child = new Node() { Name = "F" } },
        }
    }
};

// Output will hold the flattened tree
var output = Flatten(dict["P1"]);

List<Node> Flatten(List<Node> tree)
{
    IEnumerable<Node> SelfAndDescendents(Node node)
    {
        yield return node;
        var child = node.Child;
        // Walk the nodes to discover all children in the tree.
        while (child != null)
        {
            yield return child;
            child = child.Child;
        }
    }
    var flat = new List<Node>();
    foreach (var node in tree)
    {
        flat.AddRange(SelfAndDescendents(node));
    }
    return flat;
}

class Node
{
    public string Name { get; set; }
    public Node Child { get; set; }
}

CodePudding user response：

readonly Dictionary<string, List<string>> _lookup = new()
{
    { "P1", new() { "A", "B", "C", "D" } },
    { "B", new() { "E" } },
    { "D", new() { "F" } },
    // { "E", new() { "B" } }, // a cycle between 'B' and 'E' is handled and won't affect the output
};

private void GetKidsOfNode(string root,
    HashSet<string> visitedNodes,
    HashSet<string> kids)
{
    if (!_lookup.ContainsKey(root)) return;
    foreach (var node in _lookup[root])
    {
        if (visitedNodes.Contains(node)) continue;
        visitedNodes.Add(node);
        kids.Add(node);
        GetKidsOfNode(node, visitedNodes, kids);
    }
}


[Test]
public void Test_GetKidsOfNode()
{
    var kids = new HashSet<string>();
    var visitedNodes = new HashSet<string>();
    GetKidsOfNode("P1", visitedNodes, kids);
    Console.WriteLine(string.Join(", ", kids.ToList()));
}

Output

A, B, E, C, D, F