[자료구조 자료구조] Random Conneced Graph(minimum cost tree)

소개

최소 신장 트리 알고리즘 3가지를 이용하는 소스입니다.

C 언어로 작성되었습니다.

kruskal, prim, sollin 알고리즘을 모두 사용했구요.

하나의 파일 안에서 함수로 따로 구현되어 있습니다.

필요에 따라 따로 분리하셔도 됩니다.

다음 노드들을 포함하는 random connected graph를 만들고
10, 100, 1000, 10000

minimum cost tree를 kruskal , prim, sollin’s algorithm을 이용하여 만든다.

(평가)
10개의 노드를 포함하는 graph
출력
노드 좌표(x,y)
각 minimum cost spanning tree의 adjacency list
각 minimum cost spanning tree의 edge(v1,v2), weight(distance)

목차

총 8파일

randConnGraph.c
RandomConnectedGraph.dsp
RandomConnectedGraph.dsw
RandomConnectedGraph.exe
RandomConnectedGraph.ncb
RandomConnectedGraph.opt
RandomConnectedGraph.plg
과제설명.ppt

본문내용

void createVertex(list_pointer *headArray);
void createEdge(list_pointer *headArray);

void printAdjList(list_pointer *headArray);
void printXY(list_pointer *headArray);
void printEdge(edge_pointer *edgeArray);

void finalizingGraph(list_pointer *headArray);
int doesConnect(list_pointer *headArray, int *notVisited);
void dfs(list_pointer *headArray, int v);

int isExistenceVertex(list_pointer *headArray, int x, int y);
int isExistenceEdge(list_pointer *headArray, int x, int y);

void insertChild(list_pointer *headArray, int headVertex, int linkVertex);
void copyHeadArray(list_pointer *headArray, list_pointer *copyArray);

void kruskal(list_pointer *headArray, list_pointer *headArrayKruskal, edge_pointer *edgeArray);
void vertexUnion(int *parent, int i, int j);
int rootFind(int *parent, int i);

void prim(list_pointer *headArray, list_pointer *headArrayPrim, edge_pointer *edgeArray);
int isTreeMember(int *treeVertex, int vertex, int countVertex);

void sollin(list_pointer *headArray, list_pointer *headArrayPrim, edge_pointer *edgeArray);
int doesRepetition(edge_pointer *edgeArray, int v1, int v2);
int usedEdge(int *edges[3], int v1, int v2);

short int visited[MAX_VERTICES]; // 방문한 노드인가를 체크하기 위한 배열
int countEdge; // edge의 전체 개수


void main() {
int i;
list_pointer headArray[MAX_VERTICES]; // head node를 갖고 있는 배열
list_pointer headArrayKruskal[MAX_VERTICES]; // head node를 갖고 있는 배열
list_pointer headArrayPrim[MAX_VERTICES]; // head node를 갖고 있는 배열
list_pointer headArraySollin[MAX_VERTICES]; // head node를 갖고 있는 배열

edge_pointer edgeArray[MAX_VERTICES-1]; // 최소비용신장트리의 edge 배열

srand((unsigned)time(NULL));

// Head 배열 초기화
for(i=0; i<MAX_VERTICES; i++) {
headArray[i] = (list_pointer) malloc(sizeof(list_pointer));
headArray[i]->vertex = -1;
headArray[i]->x = -1;
headArray[i]->y = -1;
headArray[i]->link = NULL;
}

// 입력
createVertex(headArray); // vertex 생성
createEdge(headArray); // edge 생성

finalizingGraph(headArray); // connected 되었는지 확인하고
// connected 되지 않았다면 edge를 추가한다.
// 인쇄
printf("===========<font color=aaaaff>..</font>

참고자료

· 없음