오늘 해결할 수없는 질문이 있습니다.
티켓의 경로 인쇄
빈번한 여행자는 모든 여행 티켓을 수집합니다. 티켓에는 출발지 위치 시작 이름과 목적지 이름의 두 속성 만 있습니다. 델리에서 뉴욕까지의 예. 연말에 여행자는 모든 티켓을 모아 일년 내내 여행 계획을 세웁니다. 예상 여행 경로를 읽을 수있는 형식으로 인쇄하십시오. 그는 시작 위치를 기억하지 못합니다. 그는 여러 번 장소를 방문 할 수 있으며, 여러 번 앞뒤로 이동할 수도 있습니다.
초기에는 그래프를 만들면 (티켓 A는 B로 방향이 지정된 A-> B를 의미 함) 단순한 깊이 첫 번째 탐색을 사용하여 0도 (??) 인 노드에서 간단히 해결할 수 있다고 생각했습니다. 하지만 그 다음에는 랜덤 한 연결되지 않은 경로를 인쇄 할 수있는 솔루션을 얻는 올바른 방법이 아니라는 것을 깨달았습니다.
올바른 방법을 제안하십시오.
먼저 그래프에 오일러 트레일 (Eulerian trail) 또는 오일러주기가 있는지 확인해야합니다.
이 그래프는 오일러 사이클을 가지고 지시하는 경우, 모든 정점 정도 밖에 정도 및 제로 정도의 꼭지점 모두 동일 단일 강하게 연결된 구성 요소에 속하는 경우에만. 동등하게, 방향 그래프는 이 엣지 - 분리 된 방향 사이클로 분해되고 0이 아닌 각도를 가진 모든 정점 이 하나의 강하게 연결된 구성 요소에 속하는 경우에만 유향 곡선을 갖습니다.
A는 그래프가 오일러 흔적을 갖는다 관한 경우에만 최대 하나 개의 정점 는 (진출 차수) 경우 - (인도) = 1, 최대 하나 개의 정점 (인도) 갖는 - (out-degree) = 1, 다른 모든 버텍스는 동등한 학위가 있고 아웃도가 있으며 0이 아닌 정도의 모든 정점은 기본 무향 그래프의 단일 연결 구성 요소 에 속합니다.
그래프에 오일러주기가있는 경우 임의의 노드에서 DFS를 시작할 수 있으므로 경로가 올바른지 확인할 수 있습니다. 그래프는 오일러 흔적이있는 경우
먼저 (out-degree) − (in-degree) = 1의 노드를 찾아 source를 호출하고 (in-degree) − (out-degree) = 1와 노드를 찾아서 sink를 호출합니다. source에서 DFS를 시작하고 가능한 한 sink으로 가지 않아야합니다. 이것은 노드 sink과 다른 노드로 이동하는 사이에 다른 옵션이없는 경우에만 sink 노드를 사용해야 함을 의미합니다 (정확히는 아니지만 더 간단하게 만듭니다). 이렇게하면 올바른 흔적을 남길 수 있습니다.
"eulerian path"로 검색 –
모든 여행에 관련 항공권이 있다고 가정하면 (즉, 시카고로 비행하지 않은 다음 뉴욕으로 운전하여 보스턴으로 비행기를 타지 않았 음), A에서 B로 날아간다면, 다음 여행은 B.에서 시작해야합니다. 제한을 유지하면 연결되지 않은 임의의 경로가 생성되지 않습니다. –
@JimMischel은 우리가 현재 B 도시에 있고 목적지 (a1-b, a2-b, a3-b ...) 및 소스 (b-c1, b-c2, b) -a1, ...) 이제는 도시 B에서 어떤 경로가 먼저 연결되어 연결 경로로 연결되는지 판단하는 방법 (연결 수단 끝과 시작 지점은 항상 동일하게 유지해야 함). –