Java 웹 응용 프로그램의 순환 비순환 그래프 순회

Question

그래서 노드가 일부 작업을 나타내고 가장자리가 해당 작업 간의 데이터 흐름을 나타내는 방향 그래프를 작성할 수있는 웹 응용 프로그램을 작성합니다. 그래서 가장자리 {u, v}에 대해서, v가하기 전에 실행해야합니다. Click this link to see a sample graph

START 노드는 초기 값을 나타내며 출력을 제외한 다른 노드는 지정된대로 작업을 수행합니다. 출력 노드는 입력으로받은 값을 출력합니다.

그런 그래프를 처리하는 데 사용해야하는 알고리즘 접근법은 무엇입니까?

Answer 1

이것은 토폴로지 정렬의 완벽한 예입니다. 순회를 통해 주문 요구 사항을 따르는 세트를 만드는 가장 일반적인 알고리즘은 Kahn's Algorithm입니다. 의사 코드는 아래에서 볼 수 있으며 Wikipedia 링크의 정보는 시작할 수있을만큼 충분해야합니다.

L ← Empty list that will contain the sorted elements 
S ← Set of all nodes with no incoming edges 
while S is non-empty do 
    remove a node n from S 
    add n to tail of 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 S 
if graph has edges then 
    return error (graph has at least one cycle) 
else 
    return L (a topologically sorted order) 

"시작 노드"는 그래프에서 들어오는 가장자리를 적절하게 나타내므로 적용됩니다. 시작할 유일한 노드는 S입니다. 다른 정보를 원할 경우 의견에 알려주십시오.