데이터 구조 - 그림 - 최소 생 성 트 리 (프 림 알고리즘 과 크 루 스 칼 알고리즘)
18137 단어 데이터 구조
전송 문 (그림 의 옮 겨 다 니 기)http://blog.csdn.net/qq_33329316 / article / details / 53573798 전송 문 (그림 의 개념 과 그림 의 저장)http://blog.csdn.net/qq_33329316/article/details/53560874
최소 생 성 트 리 의 개념 을 이해 하기 전에 먼저 하나의 개념 생 성 트 리 를 이해 해 야 한다.
생 성 트 리
그림 의 생 성 트 리 는 이렇게 말 할 수 있다. 그림 의 모든 노드 를 포함 하고 모든 노드 사이 에 가장자리 가 있 지만 그림 이 연결 되 지 않 았 다.바로 N 개의 정점 이 있 고 N - 1 개의 변 이 있다.
최소 생 성 트 리 네요.
최소 생 성 트 리 는 이 생 성 트 리 의 가장자리 에 있 는 가중치 와 가장 작은 나무 입 니 다.
최소 생 성 트 리 는 무슨 소 용이 있 습 니까?
먼저 가설 을 세우다.당신 은 관광지 에 놀 러 가 려 고 합 니 다. 어떻게 길 을 선택해 야 당신 이 가장 적 게 가 고 이것 을 다 갈 수 있 습 니까?이것 이 바로 최소 생 성 트 리 의 원리 입 니 다. 어떻게 해야만 모든 노드 를 최소한 으로 옮 겨 다 니 며 끝 낼 수 있 습 니까?
두 가지 알고리즘 을 소개 하 다
1. Prim 알고리즘
2. Kruskal 알고리즘
Prim 알고리즘
사상
그림 G 의 정점 집합 을 U 로 설정 합 니 다. 먼저 그림 G 의 한 점 을 시작 점 a 로 선택 하고 이 점 을 집합 V 에 추가 한 다음 에 집합 U - V 에서 다른 점 b 를 찾 아 점 b 에서 V 의 임 의 한 점 의 가중치 가 가장 작 습 니 다. 이때 b 점도 집합 V 에 추가 합 니 다.이 를 통 해 현재 집합 V = {a, b} 은 집합 U - V 에서 다른 점 c 를 찾 아 점 c 에서 V 까지 임의의 가중치 가 가장 작 습 니 다. 이때 c 시 를 집합 V 에 추가 하여 모든 정점 이 V 에 가입 할 때 까지 MST 를 구축 합 니 다.N 개의 정점 이 있 기 때문에 이 MST 는 N - 1 개의 변 이 있 고 집합 V 에 점 하 나 를 넣 을 때마다 MST 의 변 을 찾 는 것 을 의미한다.
코드 에 따라 구체 적 으로 설명 하면 먼저 두 개의 배열 adjvex lowcost 를 만 드 는 것 이다.
저가 배열
1. 배열 에 가중치 가 저장 되 어 있 습 니 다. 구체 적 으로 말 하면 그 는 현재 생 성 된 트 리 에 저장 되 어 있 기 때문에 정점 에서 각 정점 사이 의 거리 입 니 다.2. 예 를 들 어 lowcost [1] 는 현재 생 성 된 나무 중의 정점 에서 정점 1 까지 의 가장 가 까 운 거 리 를 대표 한다.3. 정점 이 수종 을 만 들 고 있다 면 그의. lowcost 배열 에서 해당 하 는 위치 에 대한 가중치 가 0 (자신 이 있 으 면 0 입 니 다) 4. 생 성 나무의 정점 이 무엇 인지 아래 함수 에서 우 리 는 그것 의 lowcost [x] 를 0 으로 설정 한 가 게 를 잠시 후에 설명 할 것 입 니 다.
adjvex 배열
1. adjcex 알고리즘 에 저 장 된 것 은 무엇 입 니까?그 안에 저 장 된 것 은 현재 정점 에서 그 정점 까지 최근 의 가중치 가 가장 작다.위 는 현재 그 가 끊임없이 변화 하 는 위 에 있 는 lowcost 배열 도 주의 하 세 요.2. 예 를 들 어 adjvex [2] = 7. 그의 뜻 은 현재 2 정점 에서 7 정점 이 가장 가깝다 는 것 이다.
인접 행렬 의 알고리즘 구현
/*
；
adjvex lowcost
0 0 low ， 0 0 。 0
0 0 ;
For ； MIN ；
;
j = 1; k = 0; while (j < p - > N v) / / 모든 정점 을 순환 {if (lowcost [j]! = 0 & & lowcost [j] < min) {
min = lowcost [j];//
k = j;// K
//printf(" MIN %d
",min);
}
j++;
}
lowcost[j] ； ； min ；K ；adjves[k] ；
K 0 ； K ； los K - ，
*/
void MiniSpanTree(M_g *p)
{
int min,i,j,k,n;
int adjvex[M];
int lowcost[M];//
lowcost[0] = 0;// 0， V0
// lowcost 0
adjvex[0] = 0;// 0
for(i = 1; i < p->N_v;i++)
{
lowcost[i] = p->arc[0][i];//v0
adjvex[i] = 0;
}
for(i = 1;iN_v;i++)
{
min = INFINITE;//
j = 1; k = 0;
while( j < p->N_v )//
{
if(lowcost[j]!=0 && lowcost[j] < min)
{
min = lowcost [j];//
k = j;// K
//printf(" MIN %d
",min);
}
j++;
}
printf(" x y
");
printf("(%d,%d),%d
",adjvex[k],k,min);
lowcost[k] = 0;
printf("
");
for(n = 0; n < p->N_v;n++)
{
printf("%d\t",lowcost[n]);
}
printf("
");
for(j = 1; j < p->N_v;j++)
{
if(lowcost[j]!= 0 && lowcost[j] > p->arc[k][j])
{
lowcost[j] = p->arc[k][j];// lowcost
adjvex[j] = k;// K adjvex
}
}
}
} Prim 알고리즘 구체 적 실현
#include
");
scanf("%d%d",&x->N_v,&x->N_e);
printf("
");
for(i=0;i < x->N_v;i++)
{
scanf("%d",&x->vexs[i]);
// puts("sdsdsds");
}
//
for(i = 0;i < x->N_v;i++){
for(j = 0;j < x->N_v;j++)
{
x->arc[i][j] = FALL;
}
}
for( k = 0; k < x->N_e;k++)
{
printf(" （vi，vj） i, j w
");
scanf("%d%d%d",&i,&j,&w);
x->arc[i][j] = w;
x->arc[j][i] = x->arc[i][j];
}
}
void DFS (M_g *x,int i)
{
int j;
walks[i] = 1;
printf("%5d",x->vexs[i]);// ，
for( j = 0; j < x->N_v; j++)
{
if(x->arc[i][j] ==!9999)
DFS(x,j);
}
}
void DFSTraverse(M_g *x)
{
int i;
printf("
");
for(i = 0; i < x->N_v;i++)
{
walks[i] = 0;
}
for(i = 0;i < x->N_v;i++)
{
if(walks[i] == 0)
{
DFS(x,i);
}
}
printf("
");
}
void ergodic (M_g *x)
{ int i,j;
for(i=0;i< x->N_v;i++)
{
for(j=0;jN_v;j++)
{
printf("%d\t",x->arc[i][j]);
}
putchar('
');
}
}
void MiniSpanTree(M_g *p)
{
int min,i,j,k,n;
int adjvex[M];
int lowcost[M];//
lowcost[0] = 0;// 0， V0
// lowcost 0
adjvex[0] = 0;// 0
for(i = 1; i < p->N_v;i++)
{
lowcost[i] = p->arc[0][i];//v0
adjvex[i] = 0;
}
for(i = 1;iN_v;i++)
{
min = INFINITE;//
j = 1; k = 0;
while( j < p->N_v )//
{
if(lowcost[j]!=0 && lowcost[j] < min)
{
min = lowcost [j];//
k = j;// K
//printf(" MIN %d
",min);
}
j++;
}
printf(" x y
");
printf("(%d,%d),%d
",adjvex[k],k,min);
lowcost[k] = 0;
printf("
");
for(n = 0; n < p->N_v;n++)
{
printf("%d\t",lowcost[n]);
}
printf("
");
for(j = 1; j < p->N_v;j++)
{
if(lowcost[j]!= 0 && lowcost[j] > p->arc[k][j])
{
lowcost[j] = p->arc[k][j];// lowcost
adjvex[j] = k;// K adjvex
}
}
}
}
int main(){
M_g *p;
p = (M_g*)malloc(sizeof(M_g));
onCreateM_g(p);
ergodic (p);
DFSTraverse (p);
MiniSpanTree(p);
return 0;
}
/*9 15
0 1 2 3 4 5 6 7 8
0 1 10
0 5 11
1 2 18
1 6 16
1 8 12
2 8 8
2 3 22
3 8 21
3 6 24
3 7 16
3 4 20
4 5 26
4 7 7
5 6 17
6 7 19
*/
Kruskal 알고리즘
알고리즘 사상, 쉽게 말 하면 Prime 알고리즘 은 점 을 출발점 으로 하고 Kruskal 알고리즘 은 변 을 출발점 으로 하 는 것 입 니 다. 그의 대략적인 뜻 은 먼저 정점 과 변 을 모두 벗 기 고 변 의 가중치 에 따라 작은 것 에서 큰 것 으로 순서대로 정렬 한 다음 에 최소 가중치 의 변 에서 정점 을 찾 은 다음 에 순서대로 생 성 트 리 를 넣 는 것 입 니 다.
아래 그림 을 볼 수 있 습 니 다.
정렬 은 그림 2 와 같 습 니 다.인접 행렬 의 알고리즘 구현
먼저 구조 체 배열 생 성 그림 2 를 정의 합 니 다.
typedef struct
{
int begin;
int end;
int weight;
}Edge;
저장 시작 의 정점, 저장 이 끝 난 정점, 저장 변 의 가중치, 완벽 하 게 한 변 을 요약 했다.
/*
;
， Edge ； parent ；
Parent parent[0] = 1 0 1 ；
；
， ， Find 4 7 ；
parent ；
Find Parent ； parent[f] 0 ； 0 ； parent 0 。 ；
int Find (int *parent,int f)
{
while(parent[f] > 0)
f = parent[f];
return f;
}
void MiniSpanTree(LinkdeGraph *p)
{
int i,n,m;
Edge edges[M];//
int parent[M];//
// P edges 2 ； ； ；
for(i = 0; i < p->n_e; i++)
{
parent[i] = 0;
}
for( i = 0; i < p->n_e; i++)
{
n = Find(parent,edges[i].begin);
m = Find(parent,edges[i].end);
if( n!=m)
{
parent[n] = m;
printf("(%d,%d),%d",edges[i].begin,edges[i].end,edges[i].weight);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
