크루스칼의 알고리즘

이번 포스팅에서는 크루스칼 알고리즘(Kruskal Algorithm)에 대해 알아보겠습니다. 여기에서는 Kruskal 알고리즘의 복잡성, 작업, 예 및 구현도 살펴보겠습니다.

문자열을 int로 변환 java

하지만 알고리즘으로 바로 넘어가기 전에 먼저 스패닝 트리, 최소 스패닝 트리와 같은 기본 용어를 이해해야 합니다.

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

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

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

크루스칼의 알고리즘 연결된 가중치 그래프의 최소 스패닝 트리를 찾는 데 사용됩니다. 알고리즘의 주요 목표는 그래프의 모든 정점을 탐색할 수 있는 가장자리의 하위 집합을 찾는 것입니다. 전체적인 최적해에 초점을 맞추는 대신 모든 단계에서 최적해를 찾는 탐욕스러운 접근 방식을 따릅니다.

크루스칼의 알고리즘은 어떻게 작동하나요?

Kruskal의 알고리즘에서는 가중치가 가장 낮은 가장자리부터 시작하여 목표에 도달할 때까지 가장자리를 계속 추가합니다. Kruskal 알고리즘을 구현하는 단계는 다음과 같습니다.

먼저 모든 간선을 낮은 가중치에서 높은 순으로 정렬합니다.
이제 가중치가 가장 낮은 가장자리를 선택하여 스패닝 트리에 추가합니다. 추가할 에지가 순환을 생성하면 해당 에지를 거부합니다.
모든 정점에 도달할 때까지 계속해서 가장자리를 추가하면 최소 스패닝 트리가 생성됩니다.

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

Kruskal의 알고리즘은 도시 간의 전기 배선을 배치하는 데 사용될 수 있습니다.
LAN 연결을 설정하는 데 사용할 수 있습니다.

크루스칼 알고리즘의 예

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

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

위 그래프의 모서리의 가중치는 아래 표에 나와 있습니다.

가장자리	AB	교류	기원 후	하지만	기원전	CD	의
무게	1	7	10	5	삼	4	2

이제 위에 주어진 가장자리를 가중치의 오름차순으로 정렬합니다.

가장자리	AB	의	기원전	CD	하지만	교류	기원 후
무게	1	2	삼	4	5	7	10

이제 최소 신장 트리 구축을 시작해 보겠습니다.

1 단계 - 먼저 가장자리를 추가하세요. AB 무게로 1 MST로.

2 단계 - 가장자리 추가 의 무게로 2 주기를 생성하지 않으므로 MST에 연결합니다.

3단계 - 가장자리 추가 기원전 무게로 삼 사이클이나 루프를 생성하지 않기 때문에 MST에 연결됩니다.

4단계 - 이제 가장자리를 선택하세요. CD 무게로 4 사이클을 형성하지 않기 때문에 MST에.

5단계 - 그 후 가장자리를 선택하세요. 하지만 무게로 5. 이 가장자리를 포함하면 순환이 생성되므로 폐기합니다.

6단계 - 가장자리를 선택하세요 교류 무게로 7. 이 가장자리를 포함하면 순환이 생성되므로 폐기합니다.

7단계 - 가장자리를 선택하세요 기원 후 무게로 10. 이 가장자리를 포함하면 순환도 생성되므로 폐기합니다.

따라서 Kruskal 알고리즘을 사용하여 주어진 가중치 그래프로부터 얻은 최종 최소 스패닝 트리는 다음과 같습니다.

MST 비용은 = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10입니다.

이제 위 트리의 가장자리 수는 정점 수에서 1을 뺀 것과 같습니다. 따라서 알고리즘은 여기서 중지됩니다.

연산

 Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END

크루스칼 알고리즘의 복잡성

이제 Kruskal 알고리즘의 시간복잡도를 살펴보겠습니다.

자바 루프에서 벗어나다

크루스칼 알고리즘 구현

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

프로그램: C++에서 크루스칼 알고리즘을 구현하는 프로그램을 작성하세요.

 #include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes &gt;&gt; edges; for(int i = 0;i <edges;++i) { cout<> x &gt;&gt; y &gt;&gt; weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout &lt;<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>