Рекурсивный обход дерева - сохранение пути к каждому узлу

Question

Я пытаюсь создать рекурсивную функцию, которая проходит через словарь чисел, а затем выводит пройденный путь каждого узла.

Структура данных выглядит примерно так:

var tree = new Dictionary<int, List<int>>()
{
    {888, new List<int>() {44}},
    { 44, new List<int>() {183, 275, 100, 216}},
    {100, new List<int>() {299, 400}},
    {299, new List<int>() {504}},
    {216, new List<int>() {33}}
};

таким образом, древовидная структура, представляющая структуру данных, выглядит следующим образом

                 888
                /   \
               44    (many other nodes and subnodes)
           / /  \  \
        183 275 100 216
               /  \    \
              299 400   33
             /
            504

, и я хочу вернуть список списка, который выводит что-то вроде этого

[888, 44, 183]
[888, 44, 275]
[888, 44, 100, 299, 504]
[888, 44, 100, 400]
[888, 44, 216, 33]

Это то, что такдалеко, что может быть не правильно.Я могу успешно получить некоторые результаты, которые я хочу.Я думаю, что проблема заключается в том, что не удаляются узлы, у которых есть дочерние узлы, где были посещены все дочерние узлы.

public List<int[]> FindPaths(int currentNode, Dictionary<int, List<int>> tree, List<int> temp, List<int> visitedNodes)
    {
            if (tree.ContainsKey(currentNode))
            {
                if (!visitedNodes.Contains(currentNode))
                {
                    visitedNodes.Add(currentNode);
                }

                foreach (var node in tree[currentNode])
                {
                    visitedNodes.Add(node);
                    temp.Add(node);
                    // call method again with new values
                    FindPaths(node, tree, temp, visitedNodes);                                            
                }

                // if node has no children left and is not a leaf node
                // do something here?
            }
            else // we have reached a leaf node
            {
                paths.Add(temp.ToArray());
                temp.RemoveAt(temp.Count - 1);
                return paths;
            }
            return paths;
    }

, вызывающая функцию

paths = new List<int[]>();
var temp = new List<int>();
var vistedNodes = new List<int>();
var result = FindPaths(888, tree, temp, vistedNodes);

Может кто-нибудь помочь мне получить выходные данныеЯ хочу?Я хотел бы, чтобы это работало рекурсивно, если это возможно

Answer 1

Как и в вашем подходе, это решение состоит в том, чтобы продолжать добавлять узел при посещении, собирать список, если для этого узла нет ключа, и удалять элемент в конце его итерации.

void findPaths(int root, Dictionary<int,List<int>> tree,List<List<int>> pathList, List<int> visitedNodes)
{
    visitedNodes.Add(root);
    if(tree.ContainsKey(root))
    {
        foreach(int v in tree[root])
        {
            findPaths(v,tree,pathList,visitedNodes);
            visitedNodes.RemoveAt(visitedNodes.Count - 1);
        }
    }
    else
    {
            pathList.Add(new List<int>(visitedNodes));
    }
}

Answer 2

Решено довольно легко с использованием этого подхода

//Just some helper method
public static IEnumerable<TKey[]> GetPaths<TKey, TDictImpl>(this IDictionary<TKey, TDictImpl> dict) where TDictImpl : IEnumerable<TKey>
{
    var watchlist = new List<TKey>();
    var outlist = new List<List<TKey>>();
    GetPaths(dict, dict.Keys.First(), watchlist, outlist, new List<TKey> { dict.Keys.First() });
    return outlist.Select((l) => l.ToArray());
}
private static void GetPaths<TKey, TDictImpl>(this IDictionary<TKey, TDictImpl> dict, TKey parent, List<TKey> watchlist, List<List<TKey>> outlist, List<TKey> current) where TDictImpl : IEnumerable<TKey>
{
    //Try to get our child from the dict
    if (!dict.TryGetValue(parent, out TDictImpl subs))
    {
        //No child found, no further navigation needs to be done
        return;
    }
    foreach (var it in subs)
    {
        //Simple check to make sure we do not end in some endless loop
        if (watchlist.Contains(it))
        {
            throw new FormatException($"The key {it.ToString()} was attempted to be traversed a second time in {parent.ToString()}.");
        }
        else
        {
            watchlist.Add(it);
        }
        //Add everything to our outlist
        var tmp = current.Concat(new TKey[] { it }).ToList();
        outlist.Add(tmp);
        //Proceed with possible childnodes
        GetPaths(dict, it, watchlist, outlist, tmp);
    }
}

производит для

var tree = new Dictionary<int, List<int>>()
{
    {888, new List<int>() {44}},
    { 44, new List<int>() {183, 275, 100, 216}},
    {100, new List<int>() {299, 400}},
    {299, new List<int>() {504}},
    {216, new List<int>() {33}}
};
var res = Random.GetPaths(tree);

После вывода

[888, 44]
[888, 44, 183]
[888, 44, 275]
[888, 44, 100]
[888, 44, 100, 299]
[888, 44, 100, 299, 504]
[888, 44, 100, 400]
[888, 44, 216]
[888, 44, 216, 33]

Answer 3

Попробуйте это:

public List<List<int>> FindPaths(int currentNode, Dictionary<int,List<int>> tree)
{
    List<List<int>> paths = new List<List<int>>();

    if(tree.ContainsKey(currentNode))
    {
        foreach(var node in tree[currentNode])
        {
            var subPaths = FindPaths(node,tree);
            foreach(var subPath in subPaths)
            {
                subPath.Insert(0,currentNode);
                paths.Add(subPath);
            }
        }
    }
    else
    {
        paths.Add(new List<int>(){currentNode});
    }
    return paths;
}

Обратите внимание, что это предполагает, что у вас нет круговых путей (A-> B-> C-> A).Если словарь содержит один, вы застрянете в цикле.Если это возможно, вы должны отслеживать посещенные узлы и избегать их повторной обработки.