greedy 알고리즘을 사용하여 DAG의 모든 노드 방문

greedy 알고리즘을 사용하여 directed acyclic 그래프 내의 모든 노드를 방문하려고합니다. 깊이 첫 번째 검색과 같은 기능이 작동한다고 생각했지만 그래프를 통해 추적 할 수 없기 때문에 DAG와 어떻게 작동하는지 확신 할 수 없습니다.greedy 알고리즘을 사용하여 DAG의 모든 노드 방문

감사합니다.

출처

2013-03-06 John Smith

모든 노드를 방문하고 싶다면 왜 '스스로를 추적해야합니까?' – Raufio

왜냐하면 내가 역 추적하지 않고 그래프를 내려 간다면 반드시 모든 노드를 방문한다는 의미는 아닙니다. –

비순환 적이며 지시가있는 경우 검사 할 노드가 부족한 경우 (예 : 모든 경로의 끝까지 도달 한 경우), 방문하지 않고 노드가 존재할 수있는 위치는 어디입니까? – Raufio

예, DFS (depth-first search) 또는 너비 우선 검색 (BFS)을 사용할 수 있습니다. 좋은 texbook을 확인하십시오 (예 : "Introduction to Algorithms"Thomas H. Cormen).

"자취를 남기려면"가장자리를 사용할 필요가 없습니다. 스택 (또는 재귀) 또는 대기열을 사용하십시오.

출처

2013-03-06 07:39:38 DixonD

호출 스택을 사용하는 것이 가장 간단합니다 : –

Thomas H. Cormen의 "Introduction to Algorithms"를 확인하려면 처음에는 두려워하지 마십시오. - 모든 내용을 읽고 이해할 필요가 없습니다. 그것은 - 긴 알고리즘 학습을위한 좋은 책입니다. – Ari

@JanDvorak 예.하지만 쉽게 오버플로 할 수 있습니다. 호출 스택을 조심스럽게 사용해야합니다. – DixonD

void dfs(node V) { 
    mark V as visited; 
    for each edge E, so that E.source = V, do { 
     if(E.destination is not marked as visited) { 
      dfs(E.destination); 
     } 
    } 
}

그게 전부입니다. DFS (재귀)가 수행하는 작업은 현재 인스턴스가 완료되면 호출자 인스턴스로 돌아가는 것입니다. 모든 액티브 인스턴스를 유지하기 위해 스택을 사용하기 때문에 직접 돌아갈 필요가 없습니다. 현재 노드에서 기능이 완료되면 자동으로 이전 노드로 롤백됩니다.

출처

2013-03-06 09:53:02 aram90

알고리즘은 일반적으로 방향이없는 그래프에서 하나의 연결된 구성 요소를 찾는 데 필요합니다. DAG의 경우 노드 목록을 스캔하고 표시되지 않은 각 노드에서 해당 노드가 없어 질 때까지 dfs를 실행하여 여러 번 수행해야합니다. – didierc

예, DAG가 연결되어 있지 않으면 각 구성 요소에 대해 호출해야하지만 모든 작동 방식이며 주 아이디어는 변경되지 않습니다. – aram90

greedy 알고리즘을 사용하여 DAG의 모든 노드 방문

답변

관련 문제