DAG에서 주어진 노드 세트를 통해 모든 경로를 어떻게 찾습니까?

Question

내 응용 프로그램 사용자가 분류하는 항목 목록 (아래 파란색 노드)이 있습니다. 카테고리 자체는 그룹화 및 분류 할 수 있습니다.

결과 구조는 a로 표시 될 수 있습니다 지시 된 acyclic 그래프 (DAG) 항목이 그래프의 토폴로지 맨 아래에있는 싱크대이고 최상위 범주는 소스입니다. 범주 중 일부는 잘 정의 될 수 있지만 많은 것이 사용자 정의되어 매우 지저분해질 수 있습니다.

예시:

_{(원천: theuprightape.net)}

그 구조에서 다음 작업을 수행하고 싶습니다.

• 특정 노드 아래의 모든 항목 (싱크)을 찾으십시오 (유럽의 모든 항목)
• 모든 N 노드 세트를 통과하는 모든 경로 (있는 경우)를 찾으십시오 (example.com에서 SMTP를 통해 전송 된 모든 항목)
• 모든 노드 세트 아래에있는 모든 노드를 찾으십시오 (교차로 : Goyish Brown Foods)

첫 번째는 매우 간단 해 보입니다. 노드에서 시작하여 가능한 모든 경로를 따라 바닥까지의 항목을 수집하십시오. 그러나 더 빠른 접근 방식이 있습니까? 내가 이미 통과 한 노드를 기억하면 불필요한 반복을 피하는 데 도움이되지만 더 많은 최적화가 있습니까?

두 번째로 어떻게 가나 요? 첫 번째 단계는 세트에서 각 노드의 높이를 결정하는 것인 것 같습니다. 어떤 중 하나를 시작한 다음 나머지 세트를 포함하는 모든 경로를 찾는 모든 경로를 찾는 것입니다. 그러나 이것이 최고 (또는 심지어 좋은) 접근법입니까?

그만큼 Wikipedia에 나열된 그래프 트래버스 알고리즘 모두 특정 노드를 찾거나 두 노드 사이에서 가장 짧거나 가장 효과적인 경로를 찾는 데 관심이있는 것 같습니다. 나는 둘 다 내가 원하는 것이 아니라고 생각합니까, 아니면 이것이 내 문제에 어떻게 적용되는지 보지 못했습니까? 다른 곳은 어디에서 읽어야합니까?

Answer 1

본질적으로 3 가지 질문 모두에서 동일한 작업 인 것 같습니다. 당신은 항상 "노드 아래의 모든 x를 찾으십시오. 필요한 것은 '노드 아래의 모든 노드 찾기'(Q3을 해결)에 대한 일반적인 메커니즘 만 있으면 'Nodetype = 싱크'(Q1을 해결)의 결과를 필터링 할 수 있습니다. Q2의 경우 시작점 (노드 세트)과 엔드 포인트 (시작점 아래의 싱크)가 있으므로 솔루션 세트는 모든 경로가 싱크대에 지정된 경로입니다. 그래서 나는 당신이 기본적으로 가지고있는 것이 나무이며, 기본 트리 트래버스 알고리즘이 갈 길이라고 제안합니다.

Answer 2

그래프가 acyclic이라는 사실에도 불구하고, 당신이 인용하는 작업은 제어 흐름 그래프 분석의 유사한 측면을 상기시킵니다. 그에 따른 풍부한 알고리즘 세트가 있습니다 권세 그것은 적용 할 수 있습니다. 예를 들어, 세 번째 작업은 Computing Dominance Frontiers를 상기시킵니다. "Entry"및 "Exit"노드를 일시적으로 도입하면 알고리즘이 직접 작동한다고 생각합니다. 항목 노드는 "주어진 노드 세트"를 연결하고 종료 노드는 싱크를 연결합니다.

또한 참조하십시오 로버트 타잔 기본 알고리즘.