Kruskal 알고리즘은 최소 신장 트리 문제를 해결하는 데 사용되는 그리디 알고리즘입니다. 최소 신장 트리는 연결된 무방향 그래프에서 간선 가중치의 합이 가장 작은 신장 트리입니다. Kruskal 알고리즘은 간선 가중치가 작은 것부터 큰 것 순으로 간선을 선택합니다. 선택한 간선이 순환을 형성하지 않으면 스패닝 트리에 추가됩니다. 구체적인 구현 프로세스는 다음과 같습니다.
가장자리 가중치에 따라 모든 가장자리를 작은 것부터 큰 것까지 정렬합니다.
선택한 모서리의 두 끝점이 동일한 연결된 구성 요소에 없으면 이 모서리를 최소 스패닝 트리에 추가하고 두 끝점을 동일한 연결된 구성 요소로 병합합니다.
최소 신장 트리가 그래프의 모든 정점을 포함할 때까지.
알고리즘의 장점은 모서리의 가중치에만 주의하면 되고 꼭지점의 정도와는 관련이 없으므로 조밀한 그래프에서도 더 좋은 성능을 나타낼 수 있다는 것입니다. 동시에 Kruskal의 알고리즘은 확장성이 뛰어나고 가중치 그래프에서 최소 신장 포리스트 문제를 쉽게 처리할 수 있습니다.
모든 가장자리를 작은 것부터 큰 것까지 정렬합니다.
이 가장자리로 연결된 두 노드가 동일한 연결된 구성 요소에 있지 않으면 가장자리를 추가합니다. 스패닝 트리로 이동하여 두 노드를 연결된 구성 요소로 병합합니다.
모든 노드가 동일한 연결된 구성 요소에 있고 이때 생성된 트리가 최소 스패닝 트리가 될 때까지 2단계를 반복합니다.
구현 과정에서 일반적으로 결합 조회를 사용하여 연결을 유지함으로써 효율성을 향상시킵니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
|
이 함수는 Arrays 클래스의 정렬 메서드를 사용하여 가중치에 따라 작은 것부터 큰 것까지 가장자리를 정렬합니다. 그런 다음 함수는 정렬된 가장자리를 순서대로 탐색하고 각 가장자리에 대해 find 함수를 사용하여 해당 집합의 src 및 dest가 있는 루트 노드를 찾습니다. 루트 노드가 다르다면 두 세트가 연결되어 있지 않아 병합이 가능하다는 뜻이며, 최소 신장 트리의 결과 배열에 에지가 추가된다는 뜻이다. 마지막으로 함수는 최소 신장 트리의 결과 배열을 순회하여 각 모서리의 시작점, 끝점 및 가중치를 출력합니다.
이 구현에서는 집합을 빠르게 검색하는 방법, 즉 통합 검색을 사용하여 이를 달성합니다. 각 노드에는 상위 배열이 있으며, 여기서 parent[i]는 노드 i의 상위 노드를 나타냅니다. parent[i] == -1인 경우 노드 i는 루트 노드입니다. 노드가 위치한 집합을 검색할 때, 현재 노드의 부모 노드가 -1이면 해당 노드가 루트 노드임을 의미하고, 그렇지 않으면 부모 노드가 있는 집합을 재귀적으로 검색한다. . 두 컬렉션을 병합할 때 병합할 두 컬렉션의 루트 노드를 찾아 한 루트 노드의 상위 노드를 다른 루트 노드의 인덱스로 설정합니다. 즉, 한 컬렉션의 루트 노드를 의 루트 노드 아래에 병합합니다. 다른 컬렉션.
이렇게 구현된 Kruskal 알고리즘의 시간 복잡도는 O(ElogE)입니다. 여기서 E는 그래프의 가장자리 수를 나타냅니다. 주요 시간 비용은 가장자리를 정렬하는 과정에 있습니다. 공간 복잡도는 O(V+E)입니다. 여기서 V는 그래프의 정점 수를 나타냅니다. 주요 공간 오버헤드는 가장자리와 상위 배열을 저장하는 것입니다.
위 내용은 Kruskal 알고리즘을 구현하는 Java 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!