Алгоритм поиска пути для несортированного массива узлов - PullRequest
Новая
       72

Алгоритм поиска пути для несортированного массива узлов

0 голосов
/ 15 октября 2018

Сценарий: у меня есть карта узлов, которые связаны между собой.

  • У меня есть несортированный массив всех узлов.
  • У меня есть функция, чтобы проверить, подключены ли узлы друг к другу (если узел1 подключен к узлу2).

function areNodesConnected(node1, node2) return true/false;

Запрос: Я ищудля алгоритма (псевдокода), чтобы найти путь между 2 случайными узлами, использующими эту функцию.

Результатом должен быть отсортированный массив узлов из узла 1 в начале и узла 2 в конце массива.Если между двумя узлами нет пути, верните ноль.

Примечания:

  • нет необходимости в кратчайшем маршруте
  • , если путь больше, выберитепервая возможность

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

1 Ответ

0 голосов
/ 02 мая 2019

Мы можем использовать DFS (поиск в глубину), чтобы найти ответ.

Позволяет поддерживать стек и посещенный массив для отслеживания ранее посещенных узлов.Нам также необходимо отслеживать родительские узлы для окончательного ответа.Проверьте края, используя функцию areNodesConnected (node1, node2), как описано выше.

Шаги

  1. Создайте стек, родительский массив и посещенный массив.
  2. Переместить начальный узел в стек.
  3. Пока стек не пуст: вытолкните стек и поместите все узлы, подключенные к подключенному узлу, в стек.(с функцией areNodesConnected) Следите за тем, откуда пришел узел с родительским массивом.
  4. Итерируйте по родительскому массиву для окончательного ответа.

Псевдокод 

function findPath(int start, int end, int nodes):
    stack = Stack
    parent = array of integers to keep track of parents, set every value to -1 to start with
    vis = visited array of booleans to keep track of previous nodes

    stack.push(start)
    parent[start] = start // setting the starts parent to itself so we know when to stop searching.

    while stack is not empty:
        int x = stack.pop()
        for y in range 0 to nodes:
            if areNodesConnected(x, y) and not vis[y]: // checking if there is an edge from x to y
                stack.push(y)
                parent[y] = x; // store the parent of y
        vis[x] = true

    // now we have to print our final answer

    if parent[i] == -1:
        return null // there is no path

    list = List for final answer    

    for (int i = end; parent[i] != i; i = parent[i]): // recursively set i to it's parent until it is the starting node.
        list.add(i)

    // now lets add start
    list.add(start)

    return list

Единственная проблема с вышеприведенным решением состоит в том, что список противоположен тому, что вы хотели.

...