위상 정렬 알고리즘 이론과 문제 풀이(C언어 소스 코드 포함)

선수 과목 체계 등 선행 관계가 있는 자료구조를 정렬할 때 필요한 알고리즘이 바로 위상정렬(topological sort)이다.

방향이 있는 그래프(단, 사이클이 없어야 함) 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 알고리즘이다. 

유향 그래프(방향이 있는 그래프)에서 에지 <u,v>가 있다면 정점u가 정점v를 선행한다.

 

 위상 정렬 방법

① 진입 차수(내차수)가 0인 임의의 정점 (선행자가 없는 정점) 출력

② 출력한 정점에 부착된 모든 에지들을 제거하여 진입 차수 재계산

③ 모든 정점이 제거될 때까지 ①~② 반복

④ 진입 차수가 0인 것이 없으면, 그래프가 사이클을 포함한 것으로서 해가 존재하지 않음.

 

 위상 정렬 알고리즘 (C언어)

아래와 같은 입력 형식의 사이클이 없는 방향그래프(DAG, directed acyclic graph)를 입력으로 받아서 위상 정렬하기 위한 자료구조로 변환하고, 이를 이용하여 위상 정렬하는 프로그램을 작성하라. (스택이나 큐 사용 가능)

단, 위상정렬이 가능하지 않은 경우는 - 아직 모든 정점을 출력하지 않았는데 내향 차수가 0인 정점이 없는 경우 - 불가능(‘Impossible')이라는 메시지를 출력함.

 

C언어 소스 코드

본 과제에서는 스택을 활용하여 문제를 해결했다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
#define MAX_STACK_SIZE 100

//스택 원소
typedef int element;

//스택 구조체 선언
typedef struct {
	element stack[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init(StackType *s)
{
	s->top = -1;
}
// 공백상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 배열의 원소는 element 타입으로 선언
// 관련 데이터를 구조체로 묶어서 함수의 파라미터로 전달

// 삽입 함수
void push(StackType *s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->stack[++(s->top)] = item;
}
// 삭제 함수
element pop(StackType *s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->stack[(s->top)--];
}
// 피크 함수
element peek(StackType *s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->stack[s->top];
}

typedef struct GraphNode {
	int vertex;
	struct GraphNode *link;
} GraphNode;

typedef struct GraphType {
	int n; // 정점의 개수
	GraphNode *adj_list[MAX_VERTICES];
} GraphType;

void initGraph(GraphType *g)
{
	for (int i = 0; i < MAX_VERTICES; i++)
		g->adj_list[i] = NULL;
	g->n = 0;
}

void insertEdge(GraphType *g, int u, int v)
{
	if (u >= g->n || v >= g->n)
	{
		printf("잘못된 vertex입니다.\n");
		exit(-1);
	}

	GraphNode *node = (GraphNode*)malloc(sizeof(GraphNode));
	if (!node)
	{
		printf("메모리 할당 에러\n");
		exit(-1);
	}

	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;
}

void insertVertex(GraphType *g, int v)
{
	if ((g->n) + 1 > MAX_VERTICES)
	{
		printf("vertex 추가 실패\n");
		exit(-1);
	}
	g->n++;
}

int top_sort (GraphType *g){
	int i, count=0;
	StackType s;
	GraphNode *node;

	int *in_degree = (int *)malloc(g->n * sizeof(int));

	for (i = 0; i < g->n; i++) // 초기화
		in_degree[i] = 0;

	for (i = 0; i < g->n; i++) {
		GraphNode *node = g->adj_list[i]; // 정점 i에서 나오는 에지들
		while (node != NULL) {
			in_degree[node->vertex]++; //진입 차수 계산
			node = node->link;
		}
	}
	// 진입 차수가 0인 정점을 스택에 삽입
	init(&s);
	for (i = 0; i < g->n; i++) {
		if (in_degree[i] == 0) push(&s, i);
	}

	if (is_empty(&s)) printf("Impossible"); //진입차수가 0인 정점이 아예 없으면 impossible 출력

	// 위상 순서를 생성
	while (!is_empty(&s)) {
		int w;
		w = pop(&s);
		printf("%d ", w);
		count++;
		node = g->adj_list[w]; // 각 정점의 진입 차수를 변경
		while (node != NULL) {
			int u = node->vertex;
			in_degree[u]--; // 진입 차수를 감소
			if (in_degree[u] == 0) push(&s, u);
			node = node->link; // 다음 정점
		}
	}
	free(in_degree);
	return count; //몇개의 정점이 위상정렬되었는지 반환
}

int main() {
	int vNum, eNum; //정점 개수, 에지 개수
	int u, v;
	GraphType g;
	initGraph(&g);

	FILE *fp;			//파일 포인터 선언
	fopen_s(&fp, "dag5.txt", "r");

	if (fp == NULL)			// 파일이 없거나 찾지 못한 오류 발생 시 
	{
		printf("파일 오픈 불가\n");    //화면에 오류 표시
		fclose(fp);
	}

	fscanf_s(fp, "%d %d\n", &vNum, &eNum);

	//vertex 개수만큼 추가
	for (int i = 0; i < vNum; i++)
		insertVertex(&g, i);

	while (!feof(fp)){
		fscanf_s(fp, "%d %d\n", &u, &v);
		insertEdge(&g, u, v);
	}

	printf("위상 정렬 결과 = ");
	if (vNum != top_sort(&g)) //정렬된 정점 개수와 총 정점 개수가 같지 않으면
		printf("Impossible!");

	fclose(fp);
}