Рекурсивная функция для поиска пути в List-ах

#c_sharp #рекурсия #списки #словари

Есть n-ое количество элементов в словаре:

Dictionary> dict = new Dictionary>();


В List лежат ключи связующих словарей. То есть, например, словарь с ключом '1' связывается
со словарями с ключами 1, 6, 8, 10. А словарь с ключом 90 связывается со словарями
с ключами 8, 3, 92, 138. 

dict[1] = new List(){ 87, 6, 8, 10 };
dict[90] = new List() { 8, 3, 92, 138 };


Задача - найти кратчайший путь между словарями dict[1] и dict[90] по их связям. То
есть сначала сравнить все элементы в списке словаря с ключом 1 с 90. 
Потом сравнить по-очереди каждый элемент списка в словаре с ключом '87' с 90, потом
каждый элемент списка в словаре с ключом '6' и так далее, пока не будет достигнуто
совпадение с 90.
Полученный путь нужно запомнить в отдельный List, в котором будут ключи словарей в пути.

Пример:

dict[1] = new List(){ 3, 5 };
dict[3] = new List(){ 1, 8 };
dict[5] = new List(){ 1 };
dict[8] = new List(){ 3, 90 };
dict[90] = new List() { 8 };


Нужно найти кратчайшее расстояние от dict[1] до dict[90]. Сначала сравниваем все
элементы в dict[1] с 90. Элемента 90 в списке словаря '1' нет. Ищем дальше: берём первый
элемент списка словаря с ключом '1' (3) и сравниваем элементы словаря dict[3] с 90.
Элемента 90 в списке словаря '3' нет. Берём следующий элемент списка словаря '1' (5).
Там сравниваем всего один элемент и тоже нет совпадений. 

Теперь углубляемся и рассматриваем элементы словаря '3' как отдельные словари. Т.е.
проверяем dict[1] - ничего нет. Проверяем dict[8] - совпадение. Поиск закончен!

При этом нужно запоминать путь. В качестве вывода использовать

List output = new List();


В который по порядку будут записываться ключи словарей в пути. В примере он будет
состоять из элементов:

output.Add(1);
output.Add(3);
output.Add(8);
output.Add(90);


Очевидно, нужно использовать рекурсию для прохождения по всем элементам списков.
    

Ответы

Ответ 1

Рекурсию можно использовать, но не нужно. Задача сводится к обходу графа в ширину.
Где словари - это вершины графа. А ключи доступа - ребра. Замечу, что это орграф.

Извиняйте за введение собственной системы ввода данных, писал, чтобы проверить работоспособность.
А раз написал, не грех и поделиться.

На вход поступает 2 числа, N - кол-во ключей и M - кол-во записей о этих ключах.
В следующих M строках описываются ключи в формате: 1-e число - ключ, последующие через
пробел - ключи других словарей. Далее программа требует два числа X и Y. От какого
словаря требуется найти путь к другому.

Программа выводит кратчайший путь, если таковой существует, иначе "Don't exist".

        string[] Inp = Console.ReadLine().Split(); // Заносим данные ==>>
        int N = Convert.ToInt32(Inp[0]), M = Convert.ToInt32(Inp[1]);

        Dictionary> dict = new Dictionary>();
        for (int i = 0; i < N; i++) dict[i] = new List();

        for (int i = 0; i < M; i++)
        {
            Inp = Console.ReadLine().Split();
            int Temp = Convert.ToInt32(Inp[0]) - 1;
            for (int j = 1; j < Inp.Length; j++)
            {
                dict[Temp].Add(Convert.ToInt32(Inp[j]) - 1);
            }
        }

        Inp = Console.ReadLine().Split();
        int X = Convert.ToInt32(Inp[0]) - 1, Y = Convert.ToInt32(Inp[1]) - 1; //
<<== Все еще заносим

        Queue Work = new Queue(); // BFS работает через очередь.
        bool[] Mark = new bool[N]; // Массив, в котором будем помечать посещенные словари
        int[] Log = new int[N]; // Потребуется для вывода найденного пути
        bool Exist = false; // Существует ли наш путь вообще

        Work.Enqueue(X); // см. Алгоритм BFS (обход в глубину)
        Mark[X] = true;
        Log[X] = -1;

        while (Work.Count > 0)
        {
            int v = Work.Dequeue();

            for (int i = 0; i < dict[v].Count; i++)
            {
                if (!Mark[dict[v][i]])
                {
                    if (dict[v][i] == Y) Exist = true;

                    Work.Enqueue(dict[v][i]);
                    Mark[dict[v][i]] = true;
                    Log[dict[v][i]] = v;
                }
            }
        }

        if (Exist)
        {
            List output = new List(); // Восстанавливаем путь
            for (int v = Y; v != -1; v = Log[v]) output.Add(v);

            output.Reverse();

            for (int i = 0; i < output.Count; i++) Console.Write(output[i] + 1 + " ");
            Console.WriteLine();
        }
        else Console.WriteLine("Don't exist");


Вот пример работы:

Входные данные:

100 6
1 2 3 4 5
5 2 3 1
45 42 13
54 42 13
3 45
42 54
1 13


Выходные данные:

1 3 45 13


Надеюсь, помог.