한 걸음 한 걸음 알고리즘 (크 루 스 칼 알고리즘 아래)

【 성명: 판권 소유, 전재 환영, 상업 용도 로 사용 하지 마 십시오. 연락처: feixiaoxixing @ 163. com]
    앞에서 크 루스 칼 의 알고리즘 을 토론 할 때 우 리 는 알고리즘 의 기본 과정, 기본 데이터 구조 와 알고리즘 에서 해결 해 야 할 세 가지 문제 (정렬, 판단, 합병) 를 분석 했다.오늘 우 리 는 나머지 부분의 내용 을 계속 완성 했다.합병 함수 에서 우 리 는 두 개의 기본 함수, find 를 호출 했다.tree_by_index 와 deletemini_tree_from_group, 아래 상세 한 계산 과정 을 제시 합 니 다.

MINI_GENERATE_TREE* find_tree_by_index(MINI_GENERATE_TREE* pTree[], int length, int point)
{
	int outer;
	int inner;

	for(outer = 0; outer < length; outer++){
		for(inner = 0; inner < pTree[outer]->node_num; inner ++){
			if(point == pTree[outer]->pNode[inner])
				return pTree[outer];
		}
	}

	return NULL;
}

void delete_mini_tree_from_group(MINI_GENERATE_TREE* pTree[], int length, MINI_GENERATE_TREE* pIndex)
{
	int index;

	for(index = 0; index < length; index ++){
		if(pIndex == pTree[index])
			break;
	}

	memmove(&pTree[index +1], &pTree[index], sizeof(MINI_GENERATE_TREE*) * (length -1 - index));
	return;
}

    크 루 스 칼 의 최소 생 성 트 리 를 만 들 수 있 습 니 다. 코드 는 다음 과 같 습 니 다.

MINI_GENERATE_TREE* _kruskal(MINI_GENERATE_TREE* pTree[], int length, DIR_LINE* pLine[], int number)
{
	int index;
	
	if(NULL == pTree || NULL == pLine)
		return NULL;
	
	for(index = 0; index < number; index ++){
		
		bubble_sort((void**)pLine, number, compare, swap);
		
		if(2 == isDoubleVectexExistInTree(pTree, length, pLine[index]->start, pLine[index]->end))
			continue;
		
		mergeTwoMiniGenerateTree(pTree, length, pLine[index]->start, pLine[index]->end, pLine[index]->weight);
		length --;
	}
	
	return (1 != length) ? NULL : pTree[0];
}

   위의 계산 을 하려 면 우 리 는 정점 의 개수, 선분 의 개 수 를 계산 해 야 하기 때문에 함 수 는 더욱 완선 하고 보충 해 야 한다.

MINI_GENERATE_TREE* kruskal(GRAPH* pGraph)
{
	MINI_GENERATE_TREE** pTree;
	DIR_LINE** pLine;
	int count;
	int number;

	if(NULL == pGraph)
		return NULL;

	count = pGraph->count;
	number = get_total_line_number(pGraph);

	pTree = get_tree_from_graph(pGraph);
	pLine = get_line_from_graph(pGraph);

	return _kruskal(pTree, count, pLine, number);
}

    이렇게 해서 크 루스 카 르 알고리즘 은 대체로 끝 난 셈 이다. 그 중에서 gettotal_line_number、get_tree_from_graph、get_line_from_graph 함 수 는 모두 비교적 간단 합 니 다. 여러분 은 스스로 계속 완성 할 수 있 지만 잘 테스트 해 야 합 니 다.
요약:
    (1) 코드 에서 메모리 의 방출 문 제 를 고려 하지 않 고 개선 과 향상 이 필요 합 니 다.
    (2) 일부 코드 는 prim 알고리즘 의 내용 을 복용 할 수 있 고 데이터 구조 도 같다
    (3) 알고리즘 의 작성 은 이해 하 는 것 이 중요 하 다. 절차 가 맞 으 면 테스트 까지 하면 보통 문제 가 크 지 않다.