원더랜드(프림)
47
15 asked
제가 다익스트라 알고리즘이랑 헷갈려서 질문드립니다.
프림에서는 아무 정점(ex.1번노드)를 시작 정점으로 잡고 pQ.poll하면 선생님 로직은 poll된 노드는 무조건 최소값이다라고 확정짓고 ch배열에 1로 하시는 거에서 혼동이 옵니다.
아직 다른 정점들을 다 방문하지 않았는데 왜 최소값으로 단정짓는지 모르겠습니다.
만약 시작 정점을 1로 하고 1에 연결된 다음 노드들이 1이 아닌 다른 노드들에서 오는 값이 최소일 거라는 가능성은 왜 배제된거죠?
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다.
님께서 프림 알고리즘과 다익스트라 알고리즘을 비교하며 헷갈리시는 부분이 있는 것 같아 이에 대해 설명드리겠습니다.
프림(Prim) 알고리즘과 다익스트라(Dijkstra) 알고리즘은 둘 다 우선순위 큐를 활용하여 그래프를 탐색하지만, 각 알고리즘의 목적과 동작 방식은 다소 다릅니다.
프림 알고리즘의 목적:
- 프림 알고리즘은 최소 스패닝 트리(MST)를 찾기 위한 알고리즘으로, 그래프의 정점을 모두 연결하는 최소 비용을 찾는 것이 목표입니다.
- 프림 알고리즘은 최소 스패닝 트리(MST)를 찾기 위한 알고리즘으로, 그래프의 정점을 모두 연결하는 최소 비용을 찾는 것이 목표입니다.
프림 알고리즘의 동작 원리:
- 시작 정점에서 연결된 간선을 기준으로 최소 비용(가장 작은 가중치)의 간선을 선택하여 트리를 구성합니다.
- 우선순위 큐는 최소 가중치 간선을 선택하기 위해 사용되며, 이는 항상 ‘현재까지’의 최적의 선택을 보장합니다.
- 동작 중 선택된 간선은 MST의 일부가 되며, 이는 다른 노드로의 최소 비용 연결을 계속해서 보장하기 때문입니다.
- 시작 정점에서 연결된 간선을 기준으로 최소 비용(가장 작은 가중치)의 간선을 선택하여 트리를 구성합니다.
초기 정점의 선택:
- 프림 알고리즘은 그래프가 연결 그래프라는 기본 가정 하에 작동하므로, 초기 정점의 선택은 결과에 영향을 미치지 않습니다. 어떤 정점에서 시작하든지 최소 스패닝 트리를 만들 수 있습니다.
- 프림 알고리즘은 그래프가 연결 그래프라는 기본 가정 하에 작동하므로, 초기 정점의 선택은 결과에 영향을 미치지 않습니다. 어떤 정점에서 시작하든지 최소 스패닝 트리를 만들 수 있습니다.
프림 알고리즘에서 pQ.poll()된 정점은 최소 가중치로 연결된 정점임을 보장합니다. 이 과정은 다익스트라와 본질적으로 유사하지만, 다익스트라는 특정 출발점에서 모든 정점으로의 최단 경로를 찾는 목적이기 때문에 프림과의 목적 차이를 이해하시면 도움이 될 것 같습니다.
관련 질문에 대해 좀 더 깊이 이해하고자 하는 경우, 아래의 답변을 참고해 보시면 도움이 될 것입니다:
- 그래프 최단거리(BFS) 질문이 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
19
1
갑자기 채점 사이트가 바뀌었어요
0
19
1
문제 리스트 페이지
0
22
1
채점 사이트 관련 질문드립니다
0
20
1
봉우리 문제 질문입니다
0
78
2
씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?
0
62
0
이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?
0
70
0
가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법
0
67
1
좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ
0
83
2
6-7 강의에서
0
47
1
6-6. 장난꾸러기 질문 있습니다.
0
43
1
강의 수강후 코딩테스트
0
106
1
answer 변수 사용 여부
0
42
1
2중 for문
1
83
2
2-11. 임시반장정하기 (Runtime Error)
0
62
1
혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?
0
68
1
이런 풀이는 어떨까요
0
42
1
자바 스트림 방식의 효율성 질문 드립니다.
0
55
1
알고리즘 자료 구조들..
0
60
1
StringBuilder vs BufferdWriter
0
47
1
이런 코드는 어떤가요?
0
59
1
bfs 풀이
0
55
1
병합정렬
0
55
1
26강 임시반장 정하기에서 질문이 있습니다
0
43
1