문제 설명
그래프 직렬화 (Graph serialization)
유향 그래프를 '직렬화'하는 간단한 알고리즘을 찾고 있습니다. 특히 실행 순서에 대한 상호 의존성을 가진 파일 세트가 있고 컴파일 타임에 올바른 순서를 찾고 싶습니다. 컴파일러는 항상 그렇게 하는 것이 상당히 일반적인 일임에 틀림없다는 것을 압니다. 하지만 오늘은 제 google‑fu가 약해졌습니다. 이에 대한 '이동' 알고리즘은 무엇입니까?
참조 솔루션
방법 1:
Topological Sort (From Wikipedia):
In graph theory, a topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts.
Pseudo code:
L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non‑empty do
remove a node n from Q
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into Q
if graph has edges then
output error message (graph has a cycle)
else
output message (proposed topologically sorted order: L)
방법 2:
I would expect tools that need this simply walk the tree in a depth‑first manner and when they hit a leaf, just process it (e.g. compile) and remove it from the graph (or mark it as processed, and treat nodes with all leaves processed as leaves).
As long as it's a DAG, this simple stack‑based walk should be trivial.
방법 3:
I've come up with a fairly naive recursive algorithm (pseudocode):
Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list
function resolve(a):
if (dest.contains(a)) return;
foreach (b in source[a]):
resolve(b);
dest.add(a);
foreach (a in source):
resolve(a);
The biggest problem with this is that it has no ability to detect cyclic dependencies ‑ it can go into infinite recursion (ie stack overflow ;‑p). The only way around that that I can see would be to flip the recursive algorithm into an interative one with a manual stack, and manually check the stack for repeated elements.
Anyone have something better?
방법 4:
If the graph contains cycles, how can there exist allowed execution orders for your files? It seems to me that if the graph contains cycles, then you have no solution, and this is reported correctly by the above algorithm.
(by Kieron、Andrew Peters、Lily Ballard、Kieron、Giorgio)