최대 유량 알고리즘을 공부하고 있습니다.
알고리즘은 이해했는데, BFS 탐색을 통해 출발지에서 목적지로 가는 경로 중 하나를 찾는 과정에서 막히네요.
예를 들어 다음과 같은 그래프가 있을 때
출발지 : 1
목적지 : 5
라고 했을 때, BFS를 돌리면
탐색순서는 1->2->3->4->5 가 될탠데
실제 5에 도착하는 경로는 1->3->5가 먼저일 거라고 생각됩니다.
이 때 이 경로를 알아내려면 어떻게 해야할까요?
그래프는 인접 정점을 linked list로 나열하는 방식으로 구현했습니다.
특정 정점에서 임의의 정점까지 가는 데 드는 최소의 간선 수와, 그 경로를 거쳐 올 때 중간 경로 중 맨 마지막 정점을 저장하세요.
댓글을 작성하려면 로그인해야 합니다.
simm4256 7년 전
최대 유량 알고리즘을 공부하고 있습니다.
알고리즘은 이해했는데, BFS 탐색을 통해 출발지에서 목적지로 가는 경로 중 하나를 찾는 과정에서 막히네요.
예를 들어 다음과 같은 그래프가 있을 때
출발지 : 1
목적지 : 5
라고 했을 때, BFS를 돌리면
탐색순서는 1->2->3->4->5 가 될탠데
실제 5에 도착하는 경로는 1->3->5가 먼저일 거라고 생각됩니다.
이 때 이 경로를 알아내려면 어떻게 해야할까요?
그래프는 인접 정점을 linked list로 나열하는 방식으로 구현했습니다.