directed acyclic graph

유향 비순환 그래프(Directed Acyclic Graph, DAG)

사이클이 없는 유향 그래프를 의미한다.

특정 그래프가 DAG인지 판별하기 위해선 다음 방법들을 사용할 수 있다.

DFS with color

노드는 다음 3가지 상태를 가진다.

• WHITE : 방문하지 않은 노드
• GRAY : 이웃 노드들 중에서 WHITE 노드가 존재하는 노드
• BLACK : 이웃 노드들 중에서 WHITE 노드가 존재하지 않는 노드

enum Color {
  WHITE,  // never visited
  GRAY,   // there are white neighber
  BLACK   // there are no white neighber
};

DFS를 진행하며 각 노드들의 현재 상태를 call stack에서 이용하고 이를 갱신하다.

현재 상태에서 현재 노드의 상태에 따라서 다음과 같이 진행한다.

• BLACK : 이미 이전에 해당 노드에 대해서 모두 노드이므로 아무것도 하지 않는다.
• WHITE : GRAY 색으로 채우고 이웃 노드들에 대해서 DAG인지 판별한다.
• GRAY : false를 반환한다. 이는 이전에 방문한 노드를 재방문 했으므로 사이클이 존재하기 때문이다.

따라서 DFS로 탐색할 때 현재 구간에서 이웃 노드들에 사이클이 있는지 여부를 판별하며 DAG인지를 판단한다.

이를 구현하면 다음과 같다.

vector<Color> colors;
vector<vector<int>> graph; // 모든 노드를 WHITE로 초기화

bool isAcyclic(int from) {
  if (colors[from] == Color::BLACK) return true;
  if (colors[from] == Color::GRAY) return false;

  colors[from] = Color::GRAY;

  for (const int &next : graph[from]) {
    bool hasCycle = !isAcyclic(next);
    if (hasCycle) return false;
  }

  colors[from] = Color::BLACK;
  return true;
}

위상 정렬

위상 정렬을 수행하며 사이클이 있는 경우를 판별할 수 있다.