[c언어] Kruskal 알고리즘을 통한 최소신장트리

소개

자료구조 과제로 제출한 과제 입니다.
간단하게 짜여진 소스라서, 형식화되어 모든 그래프에 대해 다루도록 되어 있지는 않습니다.
쉽게 이해되도록, 주석을 달아 놓았습니다.

9*9 인접행렬로 만들어진 그래프로,
main 함수에 크루스칼 알고리즘이 있습니다.

간선을 추가하고, 해당 간선으로 인해 싸이클이 발생하는지를 ,cycle_check 함수로, 확인합니다.
싸이클은, 간단하게 배열을 통해, 방문 여부를 통해서, 확인하도록 하였습니다.

컴파일 실행환경

Microsoft Visual C++ 6

본문내용

#include
#include

int graph[9][9] = {
{0,0,0,0,0,0,0,0,0},
{0,0,2,8,0,0,0,0,0},
{0,2,0,7,9,0,0,0,0},
{0,8,7,0,4,10,12,0,0},
{0,0,9,4,0,0,0,0,0},
{0,0,0,10,0,0,6,14,0},
{0,0,0,12,0,6,0,0,0},
{0,0,0,0,0,14,0,0,3},
{0,0,0,0,0,0,0,3,0}
};

int spanningtree[9][9] = {
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0}
};

int visited[9] = {0,0,0,0,0,0,0,0,0};
int def = 0; // 싸이클 체크시, 사이클 발생하면 1, 발생 안하면 0
int edge_cnt; // 간선의 개수

typedef struct edge
{
int start; // start
int finish; // destination
int weight;
} edge;

edge edgelist[10] = { 0 };

int edge_count(int graph[9][9]) ;
void reset_visited();
int cycle_check(int v, int ban);
int sequence(int s, int d);
void print_graph(int arr[9][9]);

참고자료

· 없음