[Data Structure] Topological Order (위상 정렬)

위상 정렬. 순회가 없고 방향이 있는 그래프(Directed acyclic graph)를 선후관계에 의해 정렬하는 방법이다. Stack을 이용해 구현을 하긴 했지만 다른 자료구조를 이용해도 문제는 없을 것으로 보인다. 포인터를 사용하지 않고 구현하려 애써봤지만 link 때문에 포인터가 필요하며, 그것 때문에 각 노드를 malloc 해줘야 했다. 이 이상 단순하게 짤 수 있을지 모르겠다.


#include <iostream>
#include <stdio.h>

using namespace std;

int s[100];
int s_size;
void init_s()
{
s_size = -1;
for (int i = 0; i < 100; i++){
s[i] = NULL;
}
}
int pop()
{
return s[s_size--];
}
void push(int i)
{
s[++s_size] = i;
}
int is_empty_s()
{
return s_size == -1;
}


#define MAX_NODE_NUM 100

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

int g_size;
GraphNode *adj_list[MAX_NODE_NUM];
int in_degree[MAX_NODE_NUM];

void graph_init(int n)
{
g_size = n;
for (int v = 0; v < MAX_NODE_NUM; v++){
adj_list[v] = NULL;
}
}

void insert_edge(int u, int v)
{
GraphNode *node = (GraphNode*)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = adj_list[u];
adj_list[u] = node;
}

void topo_sort()
{
for (int i = 0; i < g_size; i++){
GraphNode *node = adj_list[i];
while (node){
in_degree[node->vertex]++;
node = node->link;
}
}
init_s();
for (int i = 0; i < g_size; i++){
if (in_degree[i] == 0) push(i);
}
while (!is_empty_s()){
int w = pop();
printf("%d ", w);
GraphNode *node = adj_list[w];
while (node){
in_degree[node->vertex]--;
if (in_degree[node->vertex] == 0) push(node->vertex);
node = node->link;
}
}
return;
}

int main()
{
graph_init(6);
insert_edge(0, 2);
insert_edge(0, 3);
insert_edge(1, 3);
insert_edge(1, 4);
insert_edge(2, 3);
insert_edge(2, 5);
insert_edge(3, 5);
insert_edge(4, 5);
topo_sort();
return 0;
}