여행 티켓 문제

Question

여러 가지 교통편에 대한 여행 티켓 스택이 제공되며, 여러 가지 교통편을 이용하면 A 지점에서 B 지점으로 이동할 수 있습니다. 모든 티켓이 고장 났고 여행이 어디서 시작되는지, 끝나는 곳을 알지 못합니다. 올바른 순서로 티켓을 정렬하여 여행을 완료하십시오. 내가 생각

tickets = [ 
    {from: "Barcelona", to: "New York"} 
    {from: "Barcelona", to: "Gerona"}, 
    {from: "Madrid", to: "Barcelona"}, 
    {from: "Gerona", to: "Barcelona"} 
]

은 오른쪽 순서는 하나 그 마드리드에는 티켓, 뉴욕에서 어떤 티켓이없는

tickets = [ 
    {from: "Madrid", to: "Barcelona"}, 
    {from: "Barcelona", to: "Gerona"}, 
    {from: "Gerona", to: "Barcelona"}, 
    {from: "Barcelona", to: "New York"} 
]

때문입니다.

해당 작업에 가장 적합한 알고리즘은 무엇입니까?

언어는 JavaScript이지만 언어에 구애받지 않는 해결책이 충분할 것입니다.

업데이트 : 내가 One-way flight trip problem와 혼동하지 될 샘플 데이터를 변경했습니다.

Answer 1

노드 (도시)를 두 번 이상 방문 할 수 있다면 eulerian path problem입니다.

Here은 그래프 유형에 따라 두 가지 간단한 알고리즘으로 해결할 수 있습니다. 3 페이지의 재귀 구현은 here입니다.

Answer 2

이중 연결 목록이 아닌가요? 각 항목을 목록에 추가하고 각 항목을 적절하게 연결하십시오. 작업이 끝나면 연결되지 않은 링크가있는 두 개의 항목이 있습니다 (하나는 노드가 연결되지 않고 나머지 노드는 노드가 연결되지 않은 항목).이 노드는 시작과 끝 지점입니다. 체인, 그리고 당신이 다음에 하나 개의 항목에서 링크를 링크합니다. "에서"

Answer 3

1. 이 티켓에서 유향 그래프를 작성 부족한 항목으로 시작하여 순서를 읽어.
2. 당신의 결과를 만들 수 그래프 가장자리를 통해 모든 노드에 걸쳐 indegree 0
3. 으로 반복을 가지고있다 노드를 찾기

업데이트 : 원래 게시물에 추가 된 정보로이 솔루션이 올바른 문제를 해결하지 못합니다. 대신 IVLad의 response을보십시오.

Answer 4

당신이 가지고있는 것은 유향 그래프이며 Eulerian Path을 찾고 싶습니다. 원 티켓 (에지)에 의해

여행 (어느 것도 존재하지 않는 경우는, 어디서든 시작) 밖으로보다 더 적은 노선으로 찾기시

1. : 링크 된 기사는 기본적으로 하나를 찾는 알고리즘을 설명합니다 그래프가없는 경우 연결을 끊습니다. 그러한 티켓이 없다면, 그 티켓을 사용하십시오.
2. 티켓 (에지)를 삭제하고 결국해야

모든 티켓을 사용하는 데 반복하고, 최종 목적지.

Answer 5

다음은 자바 스크립트 구현의 샘플입니다.

var un = 
[ 
{ from:'c',to:'d'}, 
{ from:'a',to:'b'}, 
{ from:'b',to:'c'}, 
{ from:'z',to:'a'}, 
{ from:'d',to:'m'}, 
] 

function buildTable(un){ 
return un.reduce(function(previousValue, currentValue, currentIndex){ 

//build the table. 
    previousValue.from[currentValue['from']] = currentValue; 
    previousValue.to[currentValue['to']] = currentValue; 

//to find start and end.  
    if(!previousValue.from[currentValue['to']]) previousValue.from[currentValue['to']]= false; 
    if(!previousValue.to[currentValue['from']]) previousValue.to[currentValue['from']]= false; 

    return previousValue; 

},{to:{},from:{}}); 


} 

function getStart(nodes){ 
//find start node indx. 
    for(var i in nodes) 
    if(!nodes[i])return i; 
} 


function print(start,nodes){ 


var sorted = []; 
//while detecting false from buildTable structure. 
    while(start){ 
     var node = nodes[start]; 
     sorted.push(node) 
     start = node['to']; 
//console.log(start) 
    } 

return sorted; 
} 

var sorted = buildTable(un); 
console.log(print(getStart(sorted.to),sorted.from));