깊이 우선 트리에는 가장자리가 트리를 정의합니다 (예 : traversal).
다른 노드 중 일부를 연결하는 남은 가장자리가 있습니다. 교차 가장자리와 앞 가장자리의 차이점은 무엇인가요?
wikipedia에서 :
이 스패닝 트리를 기반으로 한 가장자리 원래 그래프의 세 가지 클래스로 나눌 수 있습니다. 트리의 노드에서 하위 항목 중 하나를 가리키는 앞쪽 가장자리, 노드에서 조상 중 하나를 가리키는 뒤쪽 가장자리, 둘 다하지 않는 교차 가장자리. 때로는 스패닝 트리 자체에 속하는 가장자리 인 나무 가장자리가 앞 가장자리와 별도로 분류됩니다. 원래 그래프가 방향이 지정되지 않은 경우 모든 가장자리는 트리 가장자리 또는 뒤쪽 가장자리입니다.
순회에 사용되지 않는 가장자리는 한 노드에서 다른 노드로 포인트가 상위-하위 관계를 설정합니까?
댓글
- 관련 항목 : cs.stackexchange.com/questions/99988/… 는 유 방향 그래프의 경우 교차 모서리 대신 앞쪽 모서리를 선호하는 알고리즘을 설정하려고합니다. 깊이 우선 검색.
답변
Wikipedia에 답이 있습니다.
모든 유형의 가장자리가이 그림에 나타납니다.이 그래프에서 DFS를 추적하고 (노드는 숫자 순서로 탐색 됨) 직관은 실패합니다.
이것은 다이어그램을 설명합니다 :-
앞쪽 가장자리 : (u, v), 여기서 v는 u의 후손이지만 트리 가장자리는 아닙니다. . 나무가 아닌 가장자리입니다. 정점을 DFS 트리의 하위 항목에 연결합니다.
크로스 에지 : 다른 에지. 동일한 깊이 우선 트리 또는 다른 깊이 우선 트리의 정점 사이를 이동할 수 있습니다. (layman)
그래프 G의 다른 모서리입니다. 두 개의 다른 DFS- 트리의 정점 또는 동일한 DFS- 트리의 두 정점을 연결합니다. >
댓글
- 6이 먼저 (오른쪽 먼저) 탐색되는 것이 불가능하지 않은 이유는 무엇입니까? 만약 그렇다면 2- > 3 edge는 무엇이라고 불렸을까요?
- @soandos, 알고리즘 추적에 시간을 할애하는 것이 좋습니다. Wikipedians가 실수를하지 않았다고 가정하면 ' 이미지는이 그래프에서 DFS의 진정한 실행을 설명하므로 알고리즘을이 추적에 맞추는 방법이 있습니다. 가장자리 유형은 Wikipedia에 충분히 명확하게 설명되어 있으며이 예제를 참조 할 수도 있습니다.
- 이게 DFS를 수행하는 유효한 방법이라는 것을 알고 있습니다. 그저 다른 방식으로했다면 어떻게했는지 물어 보는 것뿐입니다.
- 그러면 결과가 달라집니다. ' 죄송합니다. '이 문제를 직접 해결해야합니다.
- @soandos 일반적으로 여러 DFS 순회가 될 수 있습니다. 여기에 사용 된 개념은 주어진 하나 순회에 상대적이며 여러 순회에 대해 다릅니다.
답변
무 방향 그래프의 DFS 순회는 정점에 입사하는 모든 에지가 탐색되기 때문에 교차 에지를 남기지 않습니다.
그러나 방향성 그래프에서는 에지를 만날 수 있습니다. 그 정점이 현재 정점의 조상이나 후손이 아니도록 이전에 발견 된 정점으로 연결됩니다. 이러한 가장자리를 교차 가장자리라고합니다.
댓글
- Aporov, 응답 해 주셔서 감사합니다. Wikipedia에 표시된대로 DFS의 정점 6에 도달하면 6에서 횡단 할 세 개의 가장자리가있는 것 같습니다.이 지점에서 정점 6은 " 현재 <". 결국에는 가장자리를 정점 3으로 횡단하게됩니다. 3은 이미 방문했지만 6에서 3까지의 가장자리가 있으므로 3은 " 현재의 후손입니다. " 정점 6. 그렇다면 교차 모서리의 정의에 위배됩니다. ' 매우 명확하지 않은 정의에 더 많은 것이 있어야합니다.
- 사실 DFS에는 후면 가장자리에 대한 트리 가장자리 만 포함됩니다 (Intro to Algorithms Thm. 22.10).
답변
DFS 순회에서 노드는 모든 자식이 완료되면 완료됩니다. 끝마친. 순회 중에 각 노드의 검색 및 완료 시간을 표시하면 시작 및 종료 시간을 비교하여 노드가 하위 노드인지 확인할 수 있습니다. 실제로 모든 DFS 순회는 다음 규칙에 따라 에지를 분할합니다.
d [node]를 노드의 발견 시간으로, 마찬가지로 f [node]를 종료 시간으로 둡니다.
괄호 정리 모든 u, v에 대해 정확히 다음 중 하나가 유지됩니다.
1.d [u] < f [u] < d [v] < f [ v] 또는 d [v] < f [v] < d [u] < f [u] 그리고 u와 v 중 어느 것도 다른 것의 후손이 아닙니다.
d [u] < d [v] < f [v] < f [u] 및 v는 u의 자손입니다.
d [v] < d [u] < f [u] < f [v] 및 u는 v의 자손입니다.
그러므로 d [u] < d [v] < f [u] < f [v]는 발생할 수 없습니다.
좋아요 괄호 : () [], ([]), [()]는 괜찮지 만 ([)] 및 [(])는 괜찮지 않습니다.
예를 들어, 모서리가있는 그래프를 고려하십시오.
A-> B
A-> C
B-> C
방문 순서를 다음과 같이 표시하십시오. 노드 레이블의 문자열. 여기서 “ABCCBA”는 ((()))와 유사하게 A-> B-> C (완료) B (완료) A (완료)를 의미합니다.
따라서 “ACCBBA”는 “(() ())”의 모델이 될 수 있습니다.
예 :
“CCABBA”: 그러면 A-> C는 십자가입니다. 엣지, CC가 A의 내부가 아니기 때문입니다.
“ABCCBA”: A-> C는 전방 엣지 (간접 후손)입니다.
“ACCBBA”: A-> C는 트리 엣지 (직계 자손).
출처 :
CLRS :
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm