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

Есть 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);
Очевидно, нужно использовать рекурсию для прохождения по всем элементам списков.

Ответ

Рекурсию можно использовать, но не нужно. Задача сводится к обходу графа в ширину. Где словари - это вершины графа. А ключи доступа - ребра. Замечу, что это орграф.
Извиняйте за введение собственной системы ввода данных, писал, чтобы проверить работоспособность. А раз написал, не грех и поделиться.
На вход поступает 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
Надеюсь, помог.