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"],
])
);
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"
Всё бы ничего и мой код работал бы (чуть ниже), если бы был известен начальный маршрут от которого нужно отталкиваться.
const routes = [
['USA', 'BRA'], ['JPN', 'PHL'], ['BRA', 'UAE'], ['UAE', 'JPN']
]
const length = routes.length
const start = routes.shift()
const chain = [ start ]
while(chain.length !== length){
const [ _, to ] = chain[ chain.length -1 ]
routes.forEach(([ from ], index) => {
if(to === from){
chain.push(routes[index])
}
})
}
const set = new Set()
chain.forEach(([ from, to ]) => set.add(from).add(to))
const route = []
set.forEach(any => route.push(any))
const string = route.join(',')
console.log(string)const data = [
['A', 'B'], ['O', 'P'], // [начало], [конец (возможно)]
['E', 'F'], ['J', 'K'],
['F', 'G'], ['K', 'L'],
['N', 'O'], ['M', 'N'],
['L', 'M'], ['G', 'H'],
['B', 'C'], ['H', 'I'],
['M', 'N'], ['C', 'D'],
['D', 'E'], ['I', 'J']
]
const [ length, chain, [ start, end ], routes ] = [ data.length, [ ], [ ...data ], data.slice(2) ]
chain.push(start)
while(chain.length !== length -1){
const [ , to ] = chain[ chain.length -1 ]
routes.forEach(([ from ], index) => to === from ? chain.push(routes[ index ]) : void(0))
}
chain.push(end)
console.log(chain.map(([ from, to ], index) => index === chain.length -1 ? [ from, to ].join(',') : from).join(', '))
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
}