simm4256   7년 전

최대 유량 알고리즘을 공부하고 있습니다.

알고리즘은 이해했는데, BFS 탐색을 통해 출발지에서 목적지로 가는 경로 중 하나를 찾는 과정에서 막히네요.


예를 들어 다음과 같은 그래프가 있을 때



ff119a8aee7325cd89735c18588ee5d8.png



출발지 : 1

목적지 : 5

라고 했을 때, BFS를 돌리면

탐색순서는 1->2->3->4->5 가 될탠데

실제 5에 도착하는 경로는 1->3->5가 먼저일 거라고 생각됩니다.

이 때 이 경로를 알아내려면 어떻게 해야할까요?


그래프는 인접 정점을 linked list로 나열하는 방식으로 구현했습니다.

kipa00   7년 전

특정 정점에서 임의의 정점까지 가는 데 드는 최소의 간선 수와, 그 경로를 거쳐 올 때 중간 경로 중 맨 마지막 정점을 저장하세요.

댓글을 작성하려면 로그인해야 합니다.