언제나 휴일

[C언어 알고리즘] 7.4.2 크루스칼 알고리즘 소스 코드다음은 C언어로 작성한 크루스칼 알고리즘 소스 코드입니다. 동적 배열과 정점과 간선을 이용한 그래프를 구현하여 사용하였습니다.//Array.h#pragma oncetypedef void * Element;typedef struct _Array Array;struct _Array{        Element *base; &n..

[C언어 알고리즘] 7.4.1 크루스칼 알고리즘 구현이제 크루스칼 알고리즘을 구현하기로 해요. 이 책에서는 크루스칼 알고리즘을 구현할 때 그래프를 인접행렬로 표현하지 않고 정점과 간선의 집합체로 정의할게요. 인접행렬로 표현한 소스 코드는 인터넷이나 다른 레퍼런스에 많이 나와있으니 이를 참고하세요.   그래프는 프림 알고리즘을 구현하면서 만든 것을 사용하세요. void SelectVertex(Graph *mstree,Graph *orig..

7.4 크루스칼(Kruskal) 알고리즘(최소신장트리 알고리즘) 이번에는 크루스칼 알고리즘으로 최소신장트리를 만드는 방법을 알아봅시다.    프림 알고리즘은 최적의 정점을 선택하여 최소신장트리를 만드는 방법입니다. 반면 크루스칼 알고리즘은 최적의 간선을 선택하여 최소신장트리를 만드는 방법입니다.   크루스칼 알고리즘(graph:원본 그래프) 원본 그래프의 간선 집합을 복제 복제한 간선 집합을 비중 순으로..

[C언어 알고리즘] 7.3.3 프림 알고리즘 소스 코드다음은 C언어로 작성한 프림(Prim) 알고리즘 소스 코드입니다. 동적 배열과 정점과 간선을 이용한 그래프를 구현하여 사용하고 있습니다.//Array.h#pragma oncetypedef void * Element;typedef struct _Array Array;struct _Array{        Element *base;&nbs..

[C언어 알고리즘] 7.3.2 프림 알고리즘 구현이제 프림 알고리즘을 구현해 보아요. 프림 알고리즘에서는 최소 비용의 정점을 선택하는 내부 알고리즘이 필요해요. 프림 알고리즘에서 정점을 선택해 나갈 때 현재까지 선택한 정점에서 갈 수 있는 정점 목록에서 최소 비용의 정점을 선택해야겠죠. 이를 위해 다음과 같은 논리가 필요해요. 정점선택알고리즘(mstree:최소신장트리,graph:원본 그래프) selectedge:= NULL으로 초기화 se..