본문 바로가기
Computer Science/알고리즘

[알고리즘] ep5-3+) 위상순서 찾기

by 클레어몬트 2024. 7. 24.

문제) 주어진 방향그래프 G에 대해 다음과 같이 수행하는 프로그램을 작성하라.

1. G가 방향 비싸이클 그래프(directed acyclic graph: DAG)면 위상순서(topological order)를 구해 인쇄.

2. G에 방향 싸이클(directed cycle)이 존재하면 위상순서를 구할 수 없으므로 0을 인쇄.

 

힌트:

  1. 이 문제의 경우 그래프를 인접리스트 구조로 표현하는 것이 시간 성능 면에서 유리하며 배열로 구현하는 편이 코딩에 용이하다.
  2. 위상 정렬 알고리즘에는 두 가지 버전이 있다. 첫째 깊이우선탐색(DFS)을 응용하는 버전, 둘째 각 정점의 진입차수(in-degree)를 이용하는 버전이다. 본 문제 해결을 위해 두 번째 버전을 사용하라. 이 버전은 그래프 G가 DAG면 위상순서를 구하고 그렇지 않으면(즉, 방향싸이클이 존재하면) 일부 정점에 대해 순위를 매기지 않은 채로 정지하므로 DAG가 아님을 알 수 있다. 

주의:

  1. 방향싸이클의 존재여부 검사와 위상순서 구하기를 별도 작업으로 수행하면 전체 실행시간이 늘어나므로, 위상순서를 구하는 과정에서 방향싸이클의 존재 여부를 확인할 수 있도록 작성해야 한다.
  2. 원래 어떤 그래프에 대한 위상순서는 여러 개 있을 수 있다. 하지만 채점편의 상, 이 문제는 그 가운데 단 한 개의 위상순서만 출력 가능하도록 다음 사항을 준수해야 한다.

         1) 그래프의 부착리스트 구축 시, 새로 입력되는 간선에 대한 노드를 리스트의 맨 앞에 삽입해야 한다(이전 실습에서는 정점번호의 오               름차순으로 부착리스트 유지).

         2) 위상 정렬 알고리즘에서 최초로 진입간선의 개수가 0인 정점을 찾을 때, 정점번호 순서대로 조사해야 한다.

 

 

  

입력:

첫 번째라인: 정점 수(n)

두 번째 라인 : 정점들의 이름(단순 문자 - 예: 영문자, 숫자 등)

세 번째 라인 : 방향간선 수(m)
m개의 라인 : 방향간선 정보

 

출력:

위상순서(정점들의 이름을 인쇄)

 

 

test case1
test case1의 결과

 

 

test case2
test case2의 결과

 

 

test case3
test case3의 결과

 

 

 

 

 

(전체코드)

// 위상순서 찾기: 인접리스트 - 연결리스트 (정점의 진입차수 이용)
#include <stdio.h>
#include <stdlib.h>

// INCIDENT 구조체: 간선 정보를 저장하는 노드
typedef struct INCIDENT {
	int edgeIdx; // 간선 인덱스
	struct INCIDENT* next; // 다음 노드를 가리키는 포인터
} INCIDENT;

// EDGE 구조체: 간선 정보를 저장하는 구조체
typedef struct EDGE {
	int src; // 출발 정점
	int dest; // 도착 정점
} EDGE;

typedef struct VERTEX {
	char name;
	INCIDENT* inEdges; // 들어오는 간선 리스트
	INCIDENT* outEdges; // 나가는 간선 리스트
	int inDegree; // 진입 차수
} VERTEX;

typedef struct GRAPH {
	VERTEX* vertex; // 정점 배열
	EDGE* edge; // 간선 배열
} GRAPH;

GRAPH graph;
int g_n, g_m; // 정점 수, 간선 수
int g_topoOrder[100]; // 위상정렬 결과를 저장할 배열
int queue[100], g_front = 0, g_rear = 0;

// 함수 선언
void initializeGraph();
void buildGraph();
void insertVertex(char vName, int idx);
void insertDirectedEdge(char srcName, char destName, int idx);
int findVertexIdx(char vName);
void addFirst(INCIDENT* head, int idx);
void topologicalSort(); // 위상정렬 함수
void initQueue();
int isQueueEmpty();
void enqueue(int v);
int dequeue();

int main() {
	buildGraph();

	topologicalSort();
	if (g_topoOrder[0] == 0) { // 사이클이 있을 경우 0 출력
		printf("0"); 
	} else { // 위상정렬 결과 출력
		for (int i = 1; i <= g_n; i++) {
			printf("%c ", graph.vertex[g_topoOrder[i]].name); 
		}
	}

	return 0;
}

void initializeGraph() {
	graph.vertex = (VERTEX*)malloc(100 * sizeof(VERTEX)); // 정점 배열 동적 할당
	graph.edge = (EDGE*)malloc(1000 * sizeof(EDGE)); // 간선 배열 동적 할당
}

void buildGraph() {
	int i;
	char vName, srcName, destName;

	initializeGraph();

	scanf("%d", &g_n);
	for (i = 0; i < g_n; i++) {
		scanf(" %c", &vName);
		insertVertex(vName, i);
	}

	scanf("%d", &g_m);
	for (i = 0; i < g_m; i++) {
		scanf(" %c %c", &srcName, &destName);
		insertDirectedEdge(srcName, destName, i); // 방향 간선 삽입
	}
}

void insertVertex(char vName, int idx) {
	graph.vertex[idx].name = vName; // 정점 이름 설정

	graph.vertex[idx].outEdges = (INCIDENT*)malloc(1 * sizeof(INCIDENT)); // 나가는 간선 리스트 초기화
	graph.vertex[idx].inEdges = (INCIDENT*)malloc(1 * sizeof(INCIDENT)); // 들어오는 간선 리스트 초기화
	graph.vertex[idx].outEdges->next = NULL;
	graph.vertex[idx].inEdges->next = NULL;

	graph.vertex[idx].inDegree = 0; // 진입 차수 초기화
}

void insertDirectedEdge(char srcName, char destName, int idx) {
	int curVertexIdx = findVertexIdx(srcName); // 출발 정점 인덱스 찾기
	int adjVertexIdx = findVertexIdx(destName); // 도착 정점 인덱스 찾기
	graph.edge[idx].src = curVertexIdx;
	graph.edge[idx].dest = adjVertexIdx;

	addFirst(graph.vertex[curVertexIdx].outEdges, idx); // 출발 정점의 나가는 간선 리스트에 추가
	addFirst(graph.vertex[adjVertexIdx].inEdges, idx); // 도착 정점의 들어오는 간선 리스트에 추가

	graph.vertex[adjVertexIdx].inDegree++; // 도착 정점의 진입 차수 증가
}

int findVertexIdx(char vName) {
	for (int i = 0; i < g_n; i++) {
		if (graph.vertex[i].name == vName) {
			return i; // 정점 이름에 해당하는 인덱스 반환
		}
	}
}

void addFirst(INCIDENT* head, int idx) {
	INCIDENT* node = (INCIDENT*)malloc(1 * sizeof(INCIDENT)); // 새로운 INCIDENT 노드 생성
	node->edgeIdx = idx;
	node->next = head->next; // 리스트의 첫 부분에 삽입
	head->next = node;
}

void topologicalSort() {
	int inDegreeArr[100]; // 진입 차수 배열
	int sortIdx, curVertexIdx, adjVertexIdx;
	INCIDENT* e;

	initQueue();
	for (int i = 0; i < g_n; i++) {
		inDegreeArr[i] = graph.vertex[i].inDegree; // 각 정점의 진입 차수 설정
		if (inDegreeArr[i] == 0) { // 진입 차수가 0이면 enqueue
			enqueue(i);
		}
	}

	sortIdx = 1;
	while (!isQueueEmpty()) {
		curVertexIdx = dequeue(); // 큐에서 정점 꺼내기
		g_topoOrder[sortIdx] = curVertexIdx; // 위상정렬 결과에 추가
		sortIdx++;

		e = graph.vertex[curVertexIdx].outEdges; // 꺼낸 정점의 나가는 간선 리스트 참조
		e = e->next;
		while (e != NULL) {
			adjVertexIdx = graph.edge[e->edgeIdx].dest; // 간선의 도착 정점
			inDegreeArr[adjVertexIdx]--; // 도착 정점의 진입 차수 감소
			if (inDegreeArr[adjVertexIdx] == 0) { // 진입 차수가 0이 되면 enqueue
				enqueue(adjVertexIdx); 
			}
			e = e->next; // 다음 간선으로 이동
		}
	}

	if (sortIdx <= g_n) { // 모든 정점을 처리하지 못했다면 사이클이 존재
		g_topoOrder[0] = 0;
	} else {
		g_topoOrder[0] = 1; // 정상적으로 위상정렬 완료
	}
}

void initQueue() {
	for (int i = 0; i < 100; i++) {
		queue[i] = 0;
	}
}

int isQueueEmpty() {
	return g_front == g_rear;
}

void enqueue(int v) {
	queue[g_rear] = v;
	g_rear = (g_rear + 1) % 100;
}

int dequeue() {
	int v = queue[g_front];
	g_front = (g_front + 1) % 100;
	return v;
}

/*
3
A B C
3
A B
C A
C B

4
A B C D
6
A B
C A
C B
A D
B D
D C

8
A B C D E F G H
11
A B
C B
A D
C D
B D
D E
E F
E H
E G
F G
H G
*/

 

 

 

 

 

 

 

(추가) 다른 버전의 코드

// 위상순서 찾기: 인접리스트 - 연결리스트 (정점의 진입차수 이용)
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100
#define MAX_EDGES 1000

typedef struct NODE {
    int v; 
    struct NODE* next;
} NODE;

typedef struct GRAPH {
    int numVertex; 
    int* inDegree; // 각 정점의 진입 차수
    NODE** adjList; // 인접 리스트 배열
} GRAPH;

typedef struct QUEUE {
    int item[MAX_VERTICES]; // 큐에 저장되는 정점들
    int front; 
    int rear;
} QUEUE;

GRAPH* graph; 
int g_n, g_m; // 정점 수, 간선 수
int* g_topoOrder; // 위상정렬 결과를 저장할 배열
QUEUE* queue; 

void buildGraph();
NODE* createNode(int v);
void addEdge(int src, int dest);
void enqueue(int value);
int dequeue();
int isEmpty();
void topologicalSort(); // 위상정렬 함수

int main() {
    scanf("%d", &g_n); 
    char vertex[g_n]; // 정점을 저장할 배열
    buildGraph(); 
    for (int i = 0; i < g_n; i++) {
        scanf(" %c", &vertex[i]); // 각 정점 입력
    }
    scanf("%d", &g_m); 
    char src, dest; 
    for (int i = 0; i < g_m; i++) {
        scanf(" %c %c", &src, &dest);
        addEdge(src - 'A', dest - 'A'); // 간선 추가
    }

    topologicalSort();
	free(graph); 
	free(queue); 
    return 0;
}

void buildGraph() {
    graph = (GRAPH*)malloc(1 * sizeof(GRAPH)); 
    graph->numVertex = g_n; // 그래프의 정점 수 설정

    graph->inDegree = (int*)malloc(g_n * sizeof(int)); // 진입 차수 배열 동적 할당
    graph->adjList = (NODE**)malloc(g_n * sizeof(NODE*)); // 인접리스트 배열 동적 할당

    for (int i = 0; i < g_n; i++) {
        graph->inDegree[i] = 0; // 초기 진입 차수는 0
        graph->adjList[i] = 0; // 인접 리스트 초기화
    }
}

NODE* createNode(int v) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE)); 
    newNode->v = v; 
    newNode->next = NULL; 
    return newNode; 
}

void addEdge(int src, int dest) {
    NODE* newNode = createNode(dest); // 도착점을 가지는 새로운 노드 생성
    newNode->next = graph->adjList[src]; // 새로운 노드를 출발점 리스트에 추가
    graph->adjList[src] = newNode; // 출발점의 인접 리스트 갱신
    graph->inDegree[dest]++; // 도착점의 진입 차수 증가
}

void enqueue(int value) {
    queue->item[++queue->rear] = value;
}

int dequeue() {
    return queue->item[queue->front++];
}

int isEmpty() {
    return queue->rear < queue->front;
}

void topologicalSort() {
    queue = (QUEUE*)malloc(1 * sizeof(QUEUE));
    queue->front = 0;
    queue->rear = -1;

    int* inDegree = graph->inDegree; // 진입 차수 배열 참조
    for (int i = 0; i < graph->numVertex; i++) {
        if (inDegree[i] == 0) { // 정점의 진입 차수가 0이면 enqueue
            enqueue(i);
        }
    }

	g_topoOrder = (int*)malloc(graph->numVertex * sizeof(int));
    int cnt = 0; // 위상정렬 결과의 인덱스
    while (!isEmpty()) {
        int curV = dequeue(); // 큐에서 정점 꺼내기
        g_topoOrder[cnt++] = curV; // 위상정렬 결과 배열에 추가

        NODE* temp = graph->adjList[curV]; // 해당 정점의 인접리스트 참조
        while (temp) {
            int adjV = temp->v; // 인접한 정점
            inDegree[adjV]--; // 인접한 정점의 진입 차수 감소
            if (inDegree[adjV] == 0) { // 진입 차수가 0이 되면 enqueue
                enqueue(adjV);
            }
            temp = temp->next; // 다음 인접한 정점으로 이동
        }
    }

    if (cnt != graph->numVertex) { // 사이클이 감지되었을 때
        printf("0"); // 위상정렬 불가능을 나타내는 0을 출력
    } 
	else { // 위상정렬 결과 출력
        for (int i = 0; i < cnt; i++) { 
            printf("%c ", g_topoOrder[i] + 'A');
        }
    }
}

/*
3
A B C
3
A B
C A
C B

4
A B C D
6
A B
C A
C B
A D
B D
D C

8
A B C D E F G H
11
A B
C B
A D
C D
B D
D E
E F
E H
E G
F G
H G
*/

 

 

 

 

 

 

 

https://www.youtube.com/watch?v=caRfN1Xkw88&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=30

 

위상정렬 알고리즘에 대한 원리는 이 영상을 참고하도록 하자! 이만한 영상이 진짜 없다

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan)

저작자표시 비영리 변경금지

'Computer Science > 알고리즘' 카테고리의 다른 글

휴리스틱(heuristic) 알고리즘  (0) 2024.07.25
[알고리즘] ep5-3++) 분할통치법 vs DP  (2) 2024.07.24
[알고리즘] ep5-3) 방향그래프  (6) 2024.07.23
[알고리즘] ep5-2+) DFS, BFS 구현  (1) 2024.07.22
[알고리즘] ep5-2) 그래프 순회  (0) 2024.07.21

관련글

티스토리툴바