반응형 알고리즘3 프림(Prim) 알고리즘 이전 포스팅에서 몇가지 알고리즘에 대해서 다룬 글이 있다.자세한 내용은 아래 참고 포스팅 참고 바란다. 이번 포스팅은 프림 알고리즘 이라는것을 설명해볼 것이다. 우선 위키에서는 아래와 같이 소개한다. https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 프림 알고리즘 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소ko.wikipedia.org 좀더 쉽게 설명을 하면,시작 정점에서 연결된 가장 작은 가중치의 간선을 .. 2024. 10. 1. 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘이란.그래프의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 다익스트라 알고리즘Dijkstra Algorithm 그래프 의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하namu.wiki 다익스트라 알고리즘의 특징은 아래와 같다.장점인접 행렬 또는 우선순위 대기열을 사용하여 구현할 수 있으므로 가능한 모든 경로를 확인하는 무차별 접근 방식보다 효율적이다.거리뿐만 아니라 경로를 추적하.. 2024. 9. 29. 알고리즘 BFS 와 DFS 알고리즘 공부 해봤다면 그래프에서 모든 노드를 탐색하기 위한 기법으로 BFS와 DFS 를 들어봤을 것이다. 둘의 공통 목적으로는 다음과 같다.그래프의 탐색의 목적은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이다.그래프의 데이터는 배열처럼 정렬이 되어 있지 않다.그래프에서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.탐색 방법은 아래 그림과 같다.모든 노드를 들려야해서 효율이 떨어질순 있지만 이부분은 백트래킹으로 해결이 가능하고 백트래킹에 대한 내용은 다음포스팅에 이어서 다뤄볼 예정이다. 특징BFS 에 대한 특징BFS 는 재귀적으로 동작하지 않는다.이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한.. 2022. 8. 4. 이전 1 다음 반응형
