많은 화살표가 가능한 한 앞으로 나아갈 수 있도록 그래프를 정렬합니다.

Question

방향으로 흐르는 화살표의 수가 (정렬 순서에 비해) 최소화되도록 지시 된 그래프의 노드를 정렬해야합니다.

알고리즘을 생각할 수 있지만 (예 : 스왑이 없을 때까지 노드를 계속 교환하면) 비가 내릴 수있는 것이 얼마나 빨리 실행되는지 또는 최상의 솔루션에 도달하는지 확실하지 않습니다.

이 문제의 이름과 복잡성은 무엇입니까?

Answer 1

어떤 생각 후에 나는 문제가 두 가지로 나눌 수 있다는 것을 깨달았다.

1. 그래프의 가장 큰 acyclic 하위 그래프를 결정합니다 ( NP-HARD입니다)
2. 토폴로지로 분류합니다 (이것은) 훨씬 쉽습니다)

Answer 2

깊이 순서대로 노드를 정렬하면 토폴로지 정렬. 그러나 이것은 사이클이없는 그래프에서만 작동합니다. 그래프에 사이클이있는 것처럼 문제가 들립니다. 한 가지 옵션은 사이클을 찾는 것입니다 ( 거북이 및 토끼 알고리즘 이 작업을 수행하려면)주기를 깨고 부러진 곳을 녹음하십시오. 그런 다음 노드를 정렬하고 다시 링크하십시오.

시각화 목적 으로이 작업을 수행하는 경우 그래프 렌더링 라이브러리가 있습니다. GraphViz 그것은 당신이 묘사 한 것과 매우 유사한 일을하고 노드를 제시합니다. 통합 및 사용이 쉽고 화면 또는 다양한 출력 형식으로 렌더링됩니다.