트리 루트 찾기

Question

어떻게 노드와 모서리 집합에서 얻을 수있는 루트와 트리를 얻을 수 있습니까? (나는 연결 매트릭스로 작업하고 있는데, 각 에지에는 가중치가 있습니다 : 그래프 [i] [j], 부정적인 가장자리 없음). 나중에 DFS를 수행하고 해당 트리에서 LCA를 찾아야하므로 최적화에 도움이됩니다.

Answer 1

그래프에서 DFS 검색을하면 나무가 생깁니다 (물론 그래프가 연결된 것으로 가정).

당신은 그것을 반복 할 수 있고 각 노드에서 가능한 루트로 시작할 수 있습니다. 결국이 방법으로 스패닝 트리를 얻을 수 있습니다. 복잡성은 O (V^2 + VE)

EDIT :이 될 것입니다. 왜냐하면 임의의 유한 그래프의 경우 루트 양식 노드 a가 노드 b이면 a에서 b까지의 경로가 있기 때문입니다 트리 DFS가 만듭니다. 그래서 스패닝 트리가 있다고 가정하면 루트 V가 각 v에 도달 할 수 있습니다. 루트로 선택한 r을 반복 할 때 r에서 V의 각 v까지의 경로가 있기 때문에 스패닝 트리에서 r부터 r까지의 경로 여야합니다.

Answer 2

트리에서 하나의 노드를 선택하고 가장자리의 방향에 대해 위로 이동하십시오. 조상이없는 노드를 발견하면 루트가 있습니다.

이렇게 자주해야하는 경우 각 노드의 부모 노드를 기억하십시오.

Answer 3

나는 당신의 행렬은 directed graph G(V,E)를 들어, (즉 M[i][j]이 j이 i의 자식임을 알려줍니다) 자식 관계를 나타낸다는 것을 가정한다.

당신은 2 개 개의 다른 전략이 있습니다

• 사용 비트 벡터, 당신의 행렬의 각 셀을 통과, 셀의 무게는) null가 아닌 경우, 벡터의 자식 인덱스 표시를 : 루트가있다 (당신의 매트릭스는 열이 처음 인 경우, 또는 행) 정점은

두 번째 솔루션은 밀도 행렬에 대한 더 나은, 그 세포 모두 널 (NO 조상)이다

보면 열을 위해, 벡터에 설정되지 않았습니다. 최악의 실행 시간은 루트가 마지막 항목 (O (V²)) 일 때입니다. 이 경우 첫 번째 히트시에 멈추거나 그래프가 많은 경우 끝까지 기울이면 모든 뿌리를 얻을 수 있습니다.

첫 번째 셀은 모든 셀을 거쳐야하기 때문에 스파 스 매트릭스에 더 적합합니다. 실행 시간은 O (E)입니다. 당신은 또한이 알고리즘으로 모든 뿌리를 얻습니다.

그래프에 단 하나의 루트 만있는 것이 확실한 경우 다른 대답에서 설명한대로 가장자리를 따라 걷는 방법을 사용할 수 있습니다.

Answer 4

코드 작성이 훨씬 쉬운 계산적으로 느린 SLOWER 버전입니다. 작은 그래프의 경우에는 괜찮습니다.

학위가 0 인 노드를 찾습니다!

모든 노드도 O (n)을 계산해야하지만 설정에 따라 코드 작성이 훨씬 쉬우 며 오류가 발생하지 않습니다.