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

Question

[DZHAMBUALT]

Здраствуйте. Возможно очень странно сформулировал вопрос за это извините. Решая задачу наткнулся на одну проблему. Есть входной двумерный массив с странами:
[["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"],
  ])
);

Comments

[Alexandroppolus]

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

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

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

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

[DZHAMBUALT]

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

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

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

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

Answer 1

[Tim]

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"

Comments

[DZHAMBUALT]

Ваше решение единственное правильное. Спасибо вам

Вот что у меня в конце концов получилось

function findRoutes(routes) {
  const dictionary = {};
  const indegree = {};

  routes.forEach(([from, to]) => {
    dictionary[from] = to;
    indegree[to] = (indegree[to] || 0) + 1;
  });

  const initialRoute = Object.keys(dictionary).find((el) => {
    return !Object.keys(indegree).includes(el);
  });

  const stack = [initialRoute];

  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(", ");
}

Answer 2

[Rsa97]

В общем случае - теория графов, Эйлеров путь.
Для случая, когда путь заведомо есть, он только один и проходит через каждую вершину только один раз, ищем вершину, для которой есть исходящий маршрут, но нет входящих.
В вашем примере это "USA". Есть маршрут, который с неё начинается, но нет маршрута, который в ней заканчивается.

Comments

[DZHAMBUALT]

Я пытался что то сделать с вложенными циклами, но ничего дельного не получилось, можете помочь своим решением

Answer 3

[Akina]

Всё бы ничего и мой код работал бы (чуть ниже), если бы был известен начальный маршрут от которого нужно отталкиваться.

Ну так найдите начало (если оно гарантированно есть) или кандидата (если таковых несколько или может не быть).
То есть просто ищите значение(я), которое присутствует в первом элементе пары, но отсутствует во втором по всему массиву.

Применительно к показанному массиву - только значение USA соответствует описанному условию.

А ещё - обязательно проверяйтесь на цикл. Например, исходные (А,Б),(Б,В),(В,Б) отправят вашу программу в нирвану... Как вариант, можно просто исключать уже использованные элементы из дальнейших итераций.

Comments

[DZHAMBUALT]

Сколько не пытаюсь не получается, нужна ваша помощь

[Akina]

DZHAMBUALT, не-а, я с JScript не работаю, а копаться в доках мне тупо лень.

Answer 4

[hint000]

От исходной точки можно искать не только вперёд, но и назад.

Comments

[DZHAMBUALT]

Можете блеснуть своим кодом?

Answer 5

[Stockholm Syndrome]

function findRoute(arr) {
    const map = arr.reduce((acc, [from, to]) => (acc[from] = to, acc), {})  
    const result = []
    let curr = arr[0][0]
    while (curr) {
        result.push(curr)
        curr = map[curr]
    }
    return result
}

Comments

[DZHAMBUALT]

Ваш код работает только если точка старта находиться на [0][0]. Если я поменяю входные данные функции то результат отображается неверно. Вот примеры входных данных с выводом для вашего кода

findRoute([ ["JPN", "PHL"], ["BRA", "UAE"], ["UAE", "JPN"], ["USA", "BRA"] ])
// Вывод ['JPN', 'PHL']

findRoute([ ["BRA", "UAE"], ["JPN", "PHL"], ["UAE", "JPN"], ["USA", "BRA"] ])
// Вывод ['BRA', 'UAE', 'JPN', 'PHL']