프 림 (Prim) 알고리즘 과 크 루스 칼 (Kruskal) 알고리즘
프 림 알고리즘
사상: 이 알고리즘 은 DFS 가 옮 겨 다 니 는 것 과 비슷 하 다.생 성 트 리 에 포 함 된 점 을 끊임없이 찾 습 니 다. 생 성 트 리 에 포함 되 지 않 은 점 의 최소 값 을 찾 으 면 이 점 을 생 성 트 리 에 포함 합 니 다.마침 모든 점 을 싸 서 불필요 한 조작 이 없 기 때문에 최소 생 성 트 리 입 니 다.
알고리즘 구현;
package Prim;
import com.sun.corba.se.impl.orbutil.graph.Graph;
import com.sun.org.apache.xerces.internal.util.SynchronizedSymbolTable;
public class Prim {
public static void main(String[] args){
int[][] graph=new int[][]{{0,6,1,5,65535,65535},
{6,0,5,65535,3,65535},
{1,5,0,5,6,4},
{5,0,5,0,65535,2},
{65535,3,6,65535,0,6},
{65535,65535,4,2,6,0}};
MinTree minTree=new MinTree();
minTree.createMinTree(graph);
}
}
class MinTree{
public void createMinTree(int[][] graph) {
int i, j,k=0 ,m;
int[] lowcost = new int[6];//
int[] adjvex = new int[6];// ，
//
lowcost[0] = 0;// 0，
adjvex[0] = 0;// 0
// lowcost
for (i = 0; i < 6; i++) {
lowcost[i] = graph[0][i];// ， 65535，
adjvex[i] = 0;// vo
}
/**
* ，
* **/
for (i = 1; i < 6; i++) {//
int min = 65535;// min ， min
for (j = 1; j < 6; j++) {// lowcost
if (lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];// lowcost，
k=j;// k
}
}
System.out.println(adjvex[k]+"-"+k);
lowcost[k]=0;//
/**
* ：
* ： ，
**/
for (m=1;m<6;m++){// lowcost
if(graph[k][m]!=0&&graph[k][m]
나 는 이 알고리즘 이 세 부분 으로 나 뉜 다 고 생각한다. 첫 번 째 부분: 자신 이 설정 한 정점 을 초기 화하 고 이 점 은 임 의적 인 것 이다.
int i, j,k=0 ,m;
int[] lowcost = new int[6];//
int[] adjvex = new int[6];// ，
//
lowcost[0] = 0;// 0，
adjvex[0] = 0;// 0
// lowcost
for (i = 0; i < 6; i++) {
lowcost[i] = graph[0][i];// ， 65535，
adjvex[i] = 0;// vo
}두 번 째 부분: 생 성 트 리 에 추 가 된 점 을 lowcost 에서 최소 가중치 로 옮 겨 다 니 며 다음 최소 전 직 점 을 찾 습 니 다.여기 서 lowcost 라 는 배열 을 말 합 니 다. lowcost 의 아래 표 시 는 각 점 이 고 lowcost 값 은 현재 생 성 된 트 리 의 모든 점 에서 이 아래 표 시 된 점 까지 의 최소 가중치 입 니 다. lowcost [i] = 0 일 때 i 점 이 방문 되 었 음 을 설명 합 니 다.그러면 생 성 트 리 중 어느 점 에서 출발 했 는 지 어떻게 찾 습 니까?그럼 adjvex 배열 을 통 해 찾 아 보 세 요.3 부 는 천천히 할 게 요.
/**
* ，
* **/
for (i = 1; i < 6; i++) {//
int min = 65535;// min ， min
for (j = 1; j < 6; j++) {// lowcost
if (lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];// lowcost，
k=j;// k
}
}
System.out.println(adjvex[k]+"-"+k);//
lowcost[k]=0;// 세 번 째 부분: 두 번 째 부분 은 실행 이 끝 날 때마다 가중치 의 최소 변 의 끝 점 을 찾 아 가입 합 니 다. 그러면 이때 최소 생 성 트 리 에 점 이 하나 더 생 겼 습 니 다. 우 리 는 이 점 이 도착 할 수 있 고 생 성 트 리 에 가입 되 지 않 은 점 의 가중치 (이 가중치 가 이전 에서 특정한 점 까지 의 가중치 보다 작 으 면 저장 하지 않 습 니 다) 를 lowcost 배열 () 에 업데이트 해 야 합 니 다.다음 에 최소 값 변 을 찾 을 수 있 습 니 다.
* ：
* ： ，
**/
for (m=1;m<6;m++){// lowcost
if(graph[k][m]!=0&&graph[k][m] * ：
* ： ，
**/
for (m=1;m<6;m++){// lowcost
if(graph[k][m]!=0&&graph[k][m]
， 。 k，m 。 adjvex[ ] 。 ：
adjvex={0，5} v1 v5 。
(Kruskal )
： ， ， ， 。
：
package kruskal;
/*
* ：
* ： ， ，
* ：
* ： ， ， ， ，
* ， 。
*
*/
public class KruskalMain {
public static void main(String[] args){
// ，
Edge[] edge=new Edge[15];
for(int i=0;i<15;i++)
edge[i] =new Edge();
edge[0].begin=4;
edge[0].end=7;
edge[0].weight=7;
edge[1].begin=2;
edge[1].end=8;
edge[1].weight=8;
edge[2].begin=0;
edge[2].end=1;
edge[2].weight=10;
edge[3].begin=0;
edge[3].end=5;
edge[3].weight=11;
edge[4].begin=1;
edge[4].end=8;
edge[4].weight=12;
edge[5].begin=3;
edge[5].end=7;
edge[5].weight=16;
edge[6].begin=1;
edge[6].end=6;
edge[6].weight=16;
edge[7].begin=5;
edge[7].end=6;
edge[7].weight=17;
edge[8].begin=1;
edge[8].end=2;
edge[8].weight=18;
edge[9].begin=6;
edge[9].end=7;
edge[9].weight=19;
edge[10].begin=3;
edge[10].end=4;
edge[10].weight=20;
edge[11].begin=3;
edge[11].end=8;
edge[11].weight=21;
edge[12].begin=2;
edge[12].end=3;
edge[12].weight=22;
edge[13].begin=3;
edge[13].end=6;
edge[13].weight=24;
edge[14].begin=4;
edge[14].end=5;
edge[14].weight=26;
Kruskal kruskal=new Kruskal();
kruskal.kruskalMethod(edge);
}
}
//
class Edge
{
int begin;
int end;
int weight;
}
class Kruskal{
public void kruskalMethod(Edge[] edge){
int i,j;
int m,n;//m ，n 。
int[] parent =new int[15]; // ， ,
for(i=0;i<15;i++) // parent 0，
parent[i]=0;
for(i=0;i<15;i++) {// ，
/*
*
*/
//1.
m=find(parent,edge[i].begin);
n=find(parent,edge[i].end);
//2. ， ， n m ,
if(m!=n){
parent[m]=n;
System.out.println(edge[i].begin+"-"+edge[i].end+"="+edge[i].weight);//
}
}
}
public int find(int[] parent,int f){// ， ，
while (parent[f]>0){
f=parent[f];
}
return f;
}
}
* 알고리즘 사고: 사 이 드 를 통 해 최소 생 성 트 리 구축 *
알고리즘 프로 세 스: 하나의 사 이 드 집합 배열 을 만 들 고 작은 저장 변 의 두 정점 과 가중치 를 만 듭 니 다. 순서대로 옮 겨 다 니 면 크기 에 따라 모든 변 을 찾 을 수 있 고 출력 * 알고리즘 문 제 를 수행 할 수 있 습 니 다. 여러 변 을 만 들 때 링 * 을 만 들 수 있 습 니 다.
해결 방향: 우 리 는 하나의 배열 을 통 해 출발점 아래 에 그의 종점 아래 표 시 를 저장 합 니 다. 그러면 순서 가 있 는 것 과 같 습 니 다. 특정한 출발점 이 연 결 된 마지막 점 에 도 착 했 을 때 이 * 점 과 종점 이 도착 한 점 은 같은 점 입 니 다. 그러면 이 변 은 링 을 구성 합 니 다. *사실 이 생 성 트 리 를 연결 하 는 과정 은 그림 이 있 는 과정 과 같 습 니 다. 매번 이 점 에 다음 연결 점 이 있 는 지 확인 해 야 하기 때 문 입 니 다 *
*/
이 알고리즘 은 나의 이해 에서 세 단계 로 나 뉜 다. ：
int i,j;
int m,n;//m ，n 。
int[] parent =new int[15]; // ， ,
for(i=0;i<15;i++) // parent 0，
parent[i]=0; int i,j;
int m,n;//m ，n 。
int[] parent =new int[15]; // ， ,
for(i=0;i<15;i++) // parent 0，
parent[i]=0;
parent 라 는 배열 의 역할 은 어떤 점 이 연결 되 어 있 는 다음 점 이 있 는 지, 없 으 면 0 이 고, 있 으 면 그 점 의 아래 표 시 를 저장 하 는 것 이다. 이렇게 하 는 것 은 링 생 성 여 부 를 판단 하기 위 한 것 이다.
STEP 2: 링 여 부 를 판단 한다.
for(i=0;i<15;i++) {// ，
/*
*
*/
//1.
m=find(parent,edge[i].begin);
n=find(parent,edge[i].end); for(i=0;i<15;i++) {// ，
/*
*
*/
//1.
m=find(parent,edge[i].begin);
n=find(parent,edge[i].end);
find
public int find(int[] parent,int f){// ， ，
while (parent[f]>0){
f=parent[f];
}
return f;
링 이 되 는 조건: ， ， ， ，
* ， 。
이 부분 은 바로 이 조건 을 중심 으로 설계 한 것 이다.
세 번 째 부분: 링 이 되 는 지 여 부 를 판단 하고 링 출력 이 되 지 않 습 니 다. //2. ， ， n m ,
if(m!=n){
parent[m]=n;
System.out.println(edge[i].begin+"-"+edge[i].end+"="+edge[i].weight);//
}
}
크 루스 르 카 알고리즘 은 변 을 겨냥 하여 전개 되 었 다.변 수가 적 으 면 효율 이 높 기 때문에 희소 도 에 더 좋 고 반대로 프 림 알고리즘 은 조밀 도 를 처리 하 는 능력 이 크 루스 르 카 알고리즘 보다 높다. 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
