DFS 트리에 교차 모서리가 포함되지 않는 이유

Question

깊이 우선 검색 중에 교차 모서리가 필요하지 않은 이유는 무엇입니까?

Answer 1

크로스 에지가 있으면 더 이상 나무가 아닙니다 (나무는 사이클을 포함 할 수 없음).

n 개의 노드가있는 트리에는 n-1 개의 가장자리가 있습니다. 가장자리를 추가하는 경우 모든 가장자리 (교차, 등)에 n 가장자리가 있습니다. 이 가장자리를 추가하여 방금 연결 한 두 개의 노드에는 이미 두 개의 노드 사이에 경로가 있으므로 두 개의 노드 사이에 경로가 이미 있고이 가장자리를 추가하여 원을 닫았습니다. 이제 그래프는 더 이상 나무가 아닙니다.