알고리즘-머지-최적이진검색-최단프림

목차

소스 - 최적 이진 검색, 입력 값 : don 2.7, isa 2.7, ral 0.13, wal 0.13

소스 - 머지소트, 입력 값 : 12, 59, 34, 23, 17, 61, 31, 14

소스 - 최단경로 Prim,
입력 값 :{0,1,3,1000,1000},{1,0,3,6,1000},{3,3,0,4,2},{1000,6,4,0,5},{1000,1000,2,5,0}

본문내용

가장 작은 값을 찾아서 연결함 연결노드가 n-1 이 될때 까지
// 확장 형태로 검색을 함
void prim(int n)
{
int i , vnear , num , min ;
//모든 정점에 대하여 가장 가까운 정점을 저장할 배열
nearest = (int*)malloc(sizeof(int)*n ) ;
//각 정점에서의 최단거리 저장 배열
distance = (int*)malloc(sizeof(int)*n ) ;
for( i = 0 ; i < n ; i++ ){//초기화
nearest[i] = 1 ;
distance[i] = W[1][i] ;
}
for(int repeat = 0 ; repeat< n ; repeat++){
min = 1000 ;//최장 거리(무한대)
//각 정점에서 거리를 검사하여 다음 정점에 가장 가까운 정점을 찾음
for( i = 1 ; i< n ; i++ ){
if( 0 <= distance[i] && distance[i] < min ){
min = distance[i];
vnear = i ;
}
distance[vnear] = -1 ;//선택한 정점
//선택하지 않은 정점을 갱신
for( int ii = 1 ; ii if( W[i][vnear] < distance[i] ){
distance[i] = W[i][vnear] ;
nearest[i] = vnear ;
}
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int i, temp;
prim(5);//최단경로를 구함
for( i = 0 ; i<5 ; i++ ){
printf("%d",nearest[i]+1);
printf(" -- ");
}
printf("\n\n");
for( i = 0 ; i < 5 ; i++ )
{
if( i != nearest[i] ){
printf("%d",i+1);
printf("번 도시와 %d", nearest[i]+1);
printf("번 도시를 연결함\n");
}
}
//메모리 release
if( nearest != NULL )
free(nearest) ;
if( distance != NULL )
free(distance ) ;
scanf("%d", &temp);
return 0;
}
-------------------------------------------------------------------------------------

키워드

알고리즘,   소트,   머지,   최적이진,   최단,   프림