프림의 알고리즘 - DS 튜토리얼

이번 글에서는 프림 알고리즘에 대해 알아보겠습니다. 알고리즘과 함께 prim 알고리즘의 복잡성, 작업, 예 및 구현도 살펴보겠습니다.

본론을 시작하기에 앞서 스패닝 트리, 최소 스패닝 트리 등 기본적이고 중요한 용어에 대해 살펴보겠습니다.

스패닝 트리 - 스패닝 트리는 방향이 없는 연결 그래프의 하위 그래프입니다.

최소 스패닝 트리 - 최소 스패닝 트리는 간선의 가중치 합이 최소가 되는 스패닝 트리로 정의할 수 있습니다. 스패닝 트리의 가중치는 스패닝 트리의 가장자리에 부여된 가중치의 합입니다.

이제 주요 주제를 시작하겠습니다.

프림의 알고리즘 그래프에서 최소 스패닝 트리를 찾는 데 사용되는 그리디 알고리즘입니다. Prim의 알고리즘은 모서리 가중치의 합이 최소화될 수 있도록 그래프의 모든 꼭지점을 포함하는 모서리의 하위 집합을 찾습니다.

Prim의 알고리즘은 단일 노드로 시작하여 모든 단계에서 모든 연결 가장자리를 사용하여 모든 인접한 노드를 탐색합니다. 그래프에서 사이클을 유발하지 않는 최소 가중치를 갖는 간선이 선택되었습니다.

프림의 알고리즘은 어떻게 작동하나요?

Prim의 알고리즘은 하나의 정점에서 시작하여 목표에 도달할 때까지 가장 작은 가중치로 가장자리를 계속 추가하는 그리디 알고리즘입니다. prim의 알고리즘을 구현하는 단계는 다음과 같습니다.

먼저 무작위로 선택된 정점으로 MST를 초기화해야 합니다.
이제 위 단계의 트리를 새로운 정점과 연결하는 모든 가장자리를 찾아야 합니다. 찾은 가장자리에서 최소 가장자리를 선택하여 트리에 추가합니다.
최소 신장 트리가 형성될 때까지 2단계를 반복합니다.

prim 알고리즘의 응용은 다음과 같습니다.

Prim의 알고리즘은 네트워크 설계에 사용될 수 있습니다.
네트워크 주기를 만드는 데 사용할 수 있습니다.
전기 배선 케이블을 배치하는 데에도 사용할 수 있습니다.

프림 알고리즘의 예

이제 예제를 사용하여 prim의 알고리즘이 작동하는 것을 살펴보겠습니다. 예제를 통해 프림의 알고리즘을 이해하는 것이 더 쉬울 것입니다.

가중치 그래프가 다음과 같다고 가정합니다.

1 단계 - 먼저 위 그래프에서 정점을 선택해야 합니다. B를 선택해보자.

이런

2 단계 - 이제 정점 B에서 가장 짧은 가장자리를 선택하여 추가해야 합니다. 정점 B에서 가중치 10의 B에서 C까지의 가장자리와 가중치 4의 가장자리 B에서 D까지의 두 가장자리가 있습니다. 가장자리 중에서 가장자리 BD의 가중치가 가장 작습니다. . 따라서 MST에 추가하십시오.

3단계 - 이제 다시 모든 가장자리 중에서 가중치가 가장 작은 가장자리를 선택합니다. 이 경우 모서리 DE와 CD가 그러한 모서리입니다. 이를 MST에 추가하고 C의 인접한 부분, 즉 E와 A를 탐색합니다. 따라서 가장자리 DE를 선택하여 MST에 추가합니다.

4단계 - 이제 Edge CD를 선택하고 MST에 추가하십시오.

5단계 - 이제 엣지 CA를 선택하세요. 여기서는 그래프에 순환을 생성하므로 모서리 CE를 선택할 수 없습니다. 따라서 Edge CA를 선택하여 MST에 추가하세요.

따라서 5단계에서 생성된 그래프는 주어진 그래프의 최소 신장 트리입니다. MST 비용은 다음과 같습니다.

MST 비용 = 4 + 2 + 1 + 3 = 10단위.

연산

 Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge &apos;e&apos; connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT

Prim 알고리즘의 복잡성

이제 Prim 알고리즘의 시간복잡도를 살펴보겠습니다. 프림 알고리즘의 실행 시간은 그래프의 데이터 구조 사용과 모서리 순서에 따라 달라집니다. 아래 표에는 몇 가지 선택 사항이 나와 있습니다.

시간 복잡도

최소 모서리 가중치에 사용되는 데이터 구조	시간 복잡도
인접 행렬, 선형 검색	O(\|V\|²)
인접 목록 및 바이너리 힙	O(\|E\| 로그 \|V\|)
인접 목록과 피보나치 힙	O(\|E\|+ \|V\| 로그 \|V\|)

Prim의 알고리즘은 인접행렬이나 인접 리스트 그래프 표현을 이용하여 간단하게 구현할 수 있으며, 최소 가중치를 갖는 edge를 추가하려면 가중치 배열을 선형적으로 탐색해야 한다. O(|V|²) 시간을 실행. 알고리즘의 내부 루프에서 최소 가중치 가장자리를 찾기 위해 힙 구현을 사용하면 더욱 향상될 수 있습니다.

프림 알고리즘의 시간 복잡도는 O(E logV) 또는 O(V logV)입니다. 여기서 E는 0입니다. 가장자리의 수이고 V는 아니오입니다. 정점의.

Prim의 알고리즘 구현

이제 prim의 알고리즘 구현을 살펴보겠습니다.

프로그램: prim의 알고리즘을 C 언어로 구현하는 프로그램을 작성하세요.

 #include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
 	 weight
'); printf(' %d 
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that&apos;s all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>