[방향그래프] 위상순서 in-degree (진입차수) 이용해서 구하기

- 방향그래프 G

- 방향 비싸이클 그래프(directed acyclic graph: DAG)면 위상순서(topologicalorder)를 구해 인쇄

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

- 인접리스트 구조로 표현 && 배열로 구현

- in-degree (진입차수) 이용해서 위상순서 구하기

- 위상순서를 구하는 과정에서 방향싸이클의 존재 여부 확인

- 그래프에 대한 위상순서는 여러 개 있을 수 있지만, 아래 코드에서는 단 한 개의 위상순서만 출력 가능하도록

 

 

# include <stdio.h>
# include <stdlib.h>
# pragma warning(disable:4996)

int n, m;
int* in;
int* topOrder;
int* queue;
int queueSize = -1;

int queueIsEmpty() {
	if (queueSize == -1)
		return 1;
	else
		return 0;
}

void enQueue(int data) {
	queueSize++;
	queue[queueSize] = data;
}

int deQueue() {
	if (queueIsEmpty())
		return -1;

	int tmp = queue[0];
	for (int i = 0; i < queueSize; i++)
		queue[i] = queue[i + 1];

	queueSize--;
	return tmp;
}


typedef struct node {
	int elem;
	struct node* next;
}NODE;

typedef struct edge {
	int origin;
	int destination;
}EDGE;

typedef struct vertex {
	char name;
	int inDegree;
	struct node* outEdges;
	struct node* inEdges;
}VERTEX;

NODE* getNode() {
	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	newNode->next = NULL;
	return newNode;
}

struct graph {
	VERTEX vertices[100];
	EDGE edges[1000];
}G;// 방향그래프

int findindex(char vname) {
	for (int i = 0; i < n; i++) {
		if (G.vertices[i].name == vname)
			return i;
	}
	return -1;
}

void insertFisrt(NODE* H, int i) {
	NODE* newNode = getNode();
	newNode->elem = i;
	newNode->next = H->next;
	H->next = newNode;
	return;
}

void insertVertex(char vname, int i) {
	G.vertices[i].name = vname;
	G.vertices[i].inDegree = 0;
	G.vertices[i].inEdges = getNode();
	G.vertices[i].outEdges = getNode();
}

void insertDirectedEdge(char uname, char wname, int i) {
	int u = findindex(uname);
	int w = findindex(wname);

	G.edges[i].origin = u;
	G.edges[i].destination = w;

	insertFisrt(G.vertices[u].outEdges, i);
	insertFisrt(G.vertices[w].inEdges, i);

	G.vertices[w].inDegree++;
	return;
}

void buildGraph() {

	scanf("%d", &n);
	getchar();
	topOrder = (int*)malloc(sizeof(int) * (n + 1));
	queue = (int*)malloc(sizeof(int) * n);
	in = (int*)malloc(sizeof(int) * n);

	char vname;
	for (int i = 0; i < n; i++) {
		scanf("%c", &vname);
		insertVertex(vname, i);
		getchar();
	}

	scanf("%d", &m);
	getchar();

	char uname, wname;
	for (int i = 0; i < m; i++) {
		scanf("%c %c", &uname, &wname);
		getchar();
		insertDirectedEdge(uname, wname, i);
	}
	return;
}

void topologicalSort() {
	int t = 1;
	int u, w;

	for (int i = 0; i < n; i++)
		queue[i] = 0;

	for (int i = 0; i < n; i++) {
		in[i] = G.vertices[i].inDegree;
		if (in[i] == 0)
			enQueue(i);// in_degree가 0이면 큐에 정점 추가
	}
	while (!queueIsEmpty()) {// 큐가 빌 때까지
		u = deQueue();// 큐의 앞 요소를 T로 가져와서 append
		topOrder[t] = u;
		t++;

		NODE* tmp = G.vertices[u].outEdges->next;
		while (tmp != NULL) {// dequeue()한 정점에 인접한 정점중 방문하지 않은 정점의 in_degree를 하나 감소
			w = G.edges[tmp->elem].destination;
			in[w]--;
			if (in[w] == 0)// in_degree 감소 후 값이 0이면 해당 정점은 queue에 enqueue() 하고 방문한 것으로 표시
				enQueue(w);
			tmp = tmp->next;
		}
	}
	if (t < n + 1)
		topOrder[0] = 0;
	else
		topOrder[0] = 1;
	return;
}

int main() {

	buildGraph();
	topologicalSort();

	if (topOrder[0] == 0) {
		printf("0\n");
	}
	else {
		for (int i = 1; i <= n; i++)
			printf(" %c", G.vertices[topOrder[i]].name);
	}
	return 0;
}