Как найти начальную точку для определения маршрутов в двумерном массиве?

Question

DZHAMBUALT @DZHAMBULAT-SAMOUCHKA

Frontend разработчик

Как найти начальную точку для определения маршрутов в двумерном массиве?

Здраствуйте. Возможно очень странно сформулировал вопрос за это извините. Решая задачу наткнулся на одну проблему. Есть входной двумерный массив с странами:
[["USA", "BRA"], ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"]]

Нужно вывести правильную последовательность следования маршрутов объединив элементы массива в одну строку. Вот такой результат должен вывестись:
"USA, BRA, UAE, JPN, PHL"

Всё бы ничего и мой код работал бы (чуть ниже), если бы был известен начальный маршрут от которого нужно отталкиваться. Если поменять местами входные данные то мой код перестаёт выдавать правильную последовательность. Точка начала маршрута у меня находиться в переменной initialRoute. Пример:
[["JPN", "PHL"], ["USA", "BRA"], ["BRA", "UAE"], ["UAE", "JPN"]],
Вывод: "JPN, PHL"

Вот мой код

function findRoutes(routes) {
  const dictionary = {};
  // Точка начала маршрута 
  const initialRoute = routes[0][0];
  const stack = [initialRoute];

  routes.forEach((el) => {
    dictionary[el[0]] = el[1];
  });

  function checkRoutesPos(dictionary, initialRoute) {
    let thisRoute = initialRoute;
    let pushElem = dictionary[thisRoute];
    while (pushElem !== undefined) {
      thisRoute = dictionary[thisRoute];
      stack.push(pushElem);
      pushElem = dictionary[thisRoute];
    }
  }
  checkRoutesPos(dictionary, initialRoute);
  return stack.join(", ");
}
console.log(
  findRoutes([
    ["USA", "BRA"],
    ["JPN", "PHL"],
    ["BRA", "UAE"],
    ["UAE", "JPN"],
  ])
);
console.log(
  findRoutes([
    ["JPN", "PHL"],
    ["USA", "BRA"],
    ["BRA", "UAE"],
    ["UAE", "JPN"],
  ])
);

Вопрос задан более года назад
237 просмотров

2 комментария

Подписаться 1 Средний 2 комментария

Alexandroppolus @Alexandroppolus

Какова задача? Путь должен пройти все точки по одному разу? Повторять точки и переходы нельзя?

Какие данные гарантируются условием? Может ли быть два разных перехода из одной страны? Или в одну страну? Могут ли быть циклы?

Данные из примера выстраиваются в цепочку без циклов и ветвлений. Для такого частного случая надо найти стартовую страну (в которую нет перехода), построить хештаблицу (Map) в для переходов, чтобы быстро искать, куда летим из каждой точки, и далее циклом выстроить цепь, итого O(n) действий и несколько строк кода.

Но в общем случае всё будет куда сложнее, как по асимптотике, так и по реализации.

Написано более года назад
DZHAMBUALT @DZHAMBULAT-SAMOUCHKA Автор вопроса

Alexandroppolus, На вход приходит двумерный массив в подмассивах которого может быть только 2 элемента. Пример:
[ [Москва, Омск], [Омск, Новгород], [Новгород, Волгоград] ]

Нужно получить последовательность чтобы сохранялась вся цепочка. Вывод для выше указанного примера должен быть таким:
Москва, Омск, Новгород, Волгоград

Так как Москва начальная точка из которого идёт путь, с неё инэ начинается последовательность.
Из Москвы мы попадаем в Омск (Так как есть элемент [Москва, Омск])
из Омска в Новгород (Так как есть элемент [Омск, Новгород]),
а из Новгорода в Тюмень (Так как есть элемент [Новгород, Тюмень])

В двумерном массиве подмассивы могут быть в разном порядке. Моя проблема в том что я не могу понять как узнать от какого подмассива начинается последовательность

Написано более года назад

Какова задача? Путь должен пройти все точки по одному разу? Повторять точки и переходы нельзя?

Какие данные гарантируются условием? Может ли быть два разных перехода из одной страны? Или в одну страну? Могут ли быть циклы?

Данные из примера выстраиваются в цепочку без циклов и ветвлений. Для такого частного случая надо найти стартовую страну (в которую нет перехода), построить хештаблицу (Map) в для переходов, чтобы быстро искать, куда летим из каждой точки, и далее циклом выстроить цепь, итого O(n) действий и несколько строк кода.

Но в общем случае всё будет куда сложнее, как по асимптотике, так и по реализации.
Alexandroppolus, На вход приходит двумерный массив в подмассивах которого может быть только 2 элемента. Пример:
[ [Москва, Омск], [Омск, Новгород], [Новгород, Волгоград] ]

Нужно получить последовательность чтобы сохранялась вся цепочка. Вывод для выше указанного примера должен быть таким:
Москва, Омск, Новгород, Волгоград

Так как Москва начальная точка из которого идёт путь, с неё инэ начинается последовательность.
Из Москвы мы попадаем в Омск (Так как есть элемент [Москва, Омск])
из Омска в Новгород (Так как есть элемент [Омск, Новгород]),
а из Новгорода в Тюмень (Так как есть элемент [Новгород, Тюмень])

В двумерном массиве подмассивы могут быть в разном порядке. Моя проблема в том что я не могу понять как узнать от какого подмассива начинается последовательность

Answer 1 · 2024-03-15 20:36:55

function findSequence(input) {
    const adjacencyList = {}, indegree = {};

    input.forEach(([from, to]) => {
        adjacencyList[from] = (adjacencyList[from] || []).concat(to);
        indegree[to] = (indegree[to] || 0) + 1;
    });

    const start = Object.keys(adjacencyList).find(country => !indegree[country]);
    if (!start) {
        return false;
    }

    const result = [], visited = {};

    function dfs(node) {
        visited[node] = true;
        result.push(node);
        adjacencyList[node]?.forEach(neighbor => !visited[neighbor] && dfs(neighbor));
    }

    dfs(start);
    return result.join(', ');
}
findSequence([["USA", "BRA"], ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"]])//"USA, BRA, UAE, JPN, PHL"

Как найти начальную точку для определения маршрутов в двумерном массиве?

Войдите на сайт