Java에서 Prime 알고리즘의 원리와 구현(요약 공유)

이 기사에서는 java에 대한 관련 지식을 제공합니다. Prime 알고리즘은 연결된 그래프에서 최소 신장 트리를 구성하는 철저한 검색 알고리즘입니다. 이 글은 주로 Java에서 Prime 알고리즘의 원리와 구현을 소개합니다. 관심이 있다면 배울 수 있습니다.

추천 학습: "java 비디오 튜토리얼"

프림 알고리즘 소개

1. 마무리 터치

스패닝 트리 과정에서 이미 스패닝 트리에 있는 노드를 세트로 처리하고, 나머지 노드들을 다른 세트로 간주하고, 두 세트를 연결하는 엣지 중에서 가중치가 가장 작은 엣지를 선택할 수 있다.

2. 알고리즘 소개

먼저 노드 1과 같은 노드를 선택하고 이를 집합 U, U={1}에 넣으면 나머지 노드는 V-U={2,3,4, 5입니다. ,6,7}, 집합 V는 그래프의 모든 노드 집합입니다.

이제 두 집합(U, V-U)을 연결하는 간선 중 가중치가 가장 작은 간선을 확인하고, 가중치가 가장 작은 간선과 연결된 노드를 집합 U에 추가하면 됩니다. 위 그림에서 알 수 있듯이, 두 세트를 연결하는 3개의 간선 중에서 간선 1-2의 가중치가 가장 작습니다. 이를 선택하고 집합 U, U={1,2}, V - U=에 노드 2를 추가합니다. 아래 그림과 같이 {3,4,5,6}입니다.

그런 다음 두 세트(U 및 V-U)를 연결하는 모서리 중 가중치가 가장 작은 모서리를 선택합니다. 위 그림에서 알 수 있듯이 두 세트를 연결하는 4개의 간선 중 노드 2에서 노드 7까지의 간선 가중치가 가장 작습니다. 이 간선을 선택하고 집합 U={1,2,7}에 노드 7을 추가합니다. , V-U ={3,4,5,6}.

이렇게 U=V가 끝날 때까지 계속하면, 선택된 Edge와 모든 Node로 구성된 그래프가 최소 스패닝 트리가 됩니다. 이것이 Prim의 알고리즘입니다.

그림을 보면 집합 U에서 집합 U-V까지 어떤 간선이 가장 작은 가중치를 갖는지 쉽게 알 수 있습니다. 그러나 이러한 간선을 프로그램에서 모두 열거한 다음 최소값을 찾기에는 시간 복잡도가 너무 높습니다. 값. 이 문제는 배열을 설정하여 현명하게 해결할 수 있습니다. Closet[j]는 집합 V-U의 노드 j에서 집합 U까지의 가장 가까운 이웃 지점을 나타냅니다. Lowcost[j]는 집합 V-U의 노드 j에서 집합의 가장 가까운 이웃 지점까지의 간선 값을 나타냅니다. U를 설정합니다. 즉, 간선의 가중치(j, 가장 가까운[j])입니다.

예를 들어 위 그림에서 노드 7에서 U를 설정하는 가장 가까운 이웃 지점은 2, cloeest[7]=2입니다. 노드 7에서 가장 가까운 이웃 포인트 2까지의 에지 값은 1이며, 이는 에지(2,7)의 가중치이며 아래 그림과 같이 lowcost[7]=1로 기록됩니다.

그러니 집합 V - U에서 가장 낮은 lowcost[] 노드를 찾으세요.

3. 알고리즘 단계

1. 초기화

집합 U={u0}, u0을 V에 속하게 하고, 가장 가까운[], lowcost[] 및 s[] 배열을 초기화합니다.

2. 집합 V-U에서 가장 작은 lowcost 값을 갖는 노드 t를 찾습니다. 즉, lowcost[t]=min{lowcost[j]}, j는 V-U에 속합니다. 집합 V-U에서 U를 연결합니다.

3. 집합 U에 노드 t를 추가합니다.

4. 집합 V - U가 비어 있으면 알고리즘이 종료되고, 그렇지 않으면 5단계로 이동합니다.

5. V-U 집합의 모든 노드 j에 대해 lowcost[] 및 close[]를 업데이트합니다. if(C[t][j]

위 단계를 따르면 마침내 가중치 합이 가장 작은 스패닝 트리를 얻을 수 있습니다.

4. 다이어그램

그래프 G=(V,E)는 아래 그림과 같이 무방향 연결 가중치 그래프입니다.

1 초기화. u0=1이라고 가정하고, 집합 U={1}, 집합 V-U={2,3,4,5,6,7}, s[1]=true라고 가정하고, 배열 Nearest[]를 초기화합니다. 노드 1을 제외하고, 다른 모든 노드는 1입니다. 이는 집합 V-U의 노드에서 집합 U까지 가장 가까운 이웃 지점이 모두 1임을 의미합니다. lowcost[]: 노드 1에서 집합 V-U의 노드까지의 간선 값입니다. 가장 가까운[] 및 lowcost[]는 아래 그림에 표시되어 있습니다.

초기화 후 사진은 다음과 같습니다.

2 t=2에 해당하는 가장 작은 저비용 노드를 찾습니다. 선택된 간선과 노드는 아래와 같습니다.

3세트 U에 추가되었습니다. 집합 U, U={1,2}에 노드 t를 추가하고 동시에 V-U={3,4,5,6,7}

4를 업데이트합니다. 집합 V-U에서 t의 각 인접 점 j에 대해 t의 도움으로 업데이트될 수 있습니다. 노드 2의 인접한 점은 노드 3과 노드 7입니다.

C[2][3]=20

C[2][7]= 1< ;lowcost[7]=36, 최근접 이웃 거리 업데이트 lowcost[7]=1, 최근접 이웃 Nearest[7]=2;

업데이트된 Nearby[] 및 lowcost[]는 아래 그림과 같습니다.

업데이트된 세트는 아래와 같습니다.

5 t=7에 해당하는 가장 작은 lowcost를 갖는 노드를 찾고, 선택된 간선과 노드는 아래와 같습니다.

6 세트에 추가하세요. 집합 U, U={1,2,7}에 노드 t를 추가하고 동시에 V-U={3,4,5,6}

7을 업데이트합니다. 집합 V-U에서 t의 각 인접 점 j에 대해 t의 도움으로 업데이트될 수 있습니다. 노드 7의 인접한 점은 노드 3, 4, 5, 6입니다.

• C[7][3]=4
• C[7][4] =4< ;lowcost[4]=무한대, 가장 가까운 이웃 거리 업데이트 lowcost[3]=9, 가장 가까운 이웃 최근접[4]=7;
• C[7][5]=4
• C[7][6]=4

업데이트된 Nearest[] 및 lowcost[]는 아래 그림에 나와 있습니다.

업데이트된 세트는 아래와 같습니다.

8 t=3에 해당하는 가장 작은 lowcost를 갖는 노드를 찾고, 선택된 간선과 노드는 아래와 같습니다.

9세트 U에 추가되었습니다. 집합 U, U={1,2,3,7}에 노드 t를 추가하고 동시에 V-U={4,5,6}

10을 업데이트합니다. 집합 V-U에서 t의 각 인접 점 j에 대해 t의 도움으로 업데이트될 수 있습니다. 노드 3의 이웃은 노드 4입니다.

C[3][4]=15>lowcost[4]=9,

closest[] 및 lowcost[] 배열은 변경되지 않습니다.

업데이트된 세트는 아래와 같습니다.

11 t=4에 해당하는 가장 작은 lowcost를 갖는 노드를 찾고, 선택된 간선과 노드는 아래와 같습니다.

세트 U에 12개가 추가되었습니다. 집합 U, U={1,2,3,4,7}에 노드 t를 추가하고 동시에 V-U={5,6}

13을 업데이트합니다. 집합 V-U에서 t의 각 인접 점 j에 대해 t의 도움으로 업데이트될 수 있습니다. 노드 4의 이웃은 노드 5입니다.

C[4][5]=3

updated close[] 및 lowcost [] As 아래에 표시됩니다.

업데이트된 세트는 아래와 같습니다.

14 t=5에 해당하는 가장 작은 lowcost를 갖는 노드를 찾고, 선택된 간선과 노드는 아래와 같습니다.

15 ​​​​세트U에 추가되었습니다. 집합 U, U={1,2,3,4,5,7}에 노드 t를 추가하고 동시에 V-U={6}

16을 업데이트합니다. 집합 V-U에서 t의 각 인접 점 j에 대해 t의 도움으로 업데이트될 수 있습니다. 노드 5의 이웃은 노드 6입니다.

C[5][6]=17

업데이트된 세트는 아래와 같습니다.

17 t=6에 해당하는 가장 작은 저비용 노드를 찾습니다. 선택된 간선과 노드는 아래와 같습니다.

18이 세트 U에 추가되었습니다. 집합 U, U={1,2,3,4,5,6,7}에 노드 t를 추가하고 동시에 V-U={}

19를 업데이트합니다. 집합 V-U에서 t의 각 인접 점 j에 대해 t의 도움으로 업데이트될 수 있습니다. 노드 6에는 V-U 집합에 인접한 점이 없습니다. Nearest[] 및 lowcost[]를 업데이트할 필요가 없습니다.

20 획득한 최소 스패닝 트리는 다음과 같습니다. 최소 스패닝 트리의 가중치 합은 57입니다.

프라임 알고리즘 구현

1. 구성된 그래프

2. 테스트

추천 연구: "java 비디오 튜토리얼

"

위 내용은 Java에서 Prime 알고리즘의 원리와 구현(요약 공유)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!