[알고리즘] 위상정렬 코드 (topological sort) for DAG (Directed acyclic graph)

Directed graph에서 어떤 dependency에 의한 순서를 갖고 순회해야 하는 graph가 존재할 경우 topological sort를 사용한다.

아래 코드는 topological sort의 구현이다.

기본적으로 BFS(Breath First Search)와 유사하며, 차이점을 지닌 규칙은 매우 간단하다.

indegree (즉, 자신의 정점으로 들어오는 edge)가 0인 것 중 아무거나 부터 dequeue 해서 처리한다.

간략하게 다음과 같다.

1. 모든 정점의 indegree를 구한다.

2. indegree가 0인 모든 정점을 queue에 put 한다.

3. 모든 정점 && queue가 not empty인 동안

    1) dequeue한 것에 대해

    2) 인접 (즉, out edge가 point하는 vertex) 정점에 indegree를 모두 -1 한다.

    3) 인접 정점 중 (-1 이후) indegree가 0에 도달하면 queue에 push한다.

void graph_topological_sort(item_t *items, uint32 n, uint32 start_idx) {     uint32 i, j, k, pos;     queue<long> que;     adj_node_t *adj_node;     list_node_t *node;       int *indegree = new int[n];       for (i = 0; i < n; i++)         indegree[i] = 0;       for (i = 0; i < n; i++) {         if (RET_TYPE_FAILURE == items[i].adj_list->get_head_position(items[i].adj_list, &pos))             continue;           while (1) {             node = items[i].adj_list->get_next(items[i].adj_list, &pos);             if (NULL == node)                 break;             adj_node = (adj_node_t *)node->data;             k = item_find_slot(items, adj_node->vertex->name, n);             indegree[k]++;         }     }       for (i = 0; i < n; i++) {         if (0 == indegree[i])             que.push(i);     }       for (i = 0; i < n && !que.empty(); i++) {         j = que.front();         que.pop();         LOGD("%s -> ", items[j].vertex.name);           if (RET_TYPE_FAILURE == items[j].adj_list->get_head_position(items[j].adj_list, &pos))             continue;           while (1) {             node = items[j].adj_list->get_next(items[j].adj_list, &pos);             if (NULL == node)                 break;               adj_node = (adj_node_t *)node->data;             k = item_find_slot(items, adj_node->vertex->name, n);             indegree[k]--;             if (0 == indegree[k])                 que.push(k);         }     }       delete []indegree; }