안녕하세요
JMBOOK 2권 856page 절단점 찾기 알고리즘을 공부하던 중에
궁금한 것이 있어서 질문드리게 되었습니다.
소스 코드 28.9에서 보면,
int findCutVertex() 함수 바로 위의 주석에서
[here를 루트로 하는 서브트리에서,
역방향 간선으로 갈 수 있는 정점 중에
가장 일찍 발견된 정점의 발견 시점을 반환한다]
라고 되어 있는데요,
소스 코드의 작동을 살펴보면,
실제 그 subtree가 부모 노드보다 더 일찍 발견된 노드와
[역방향 간선]으로 연결되어있는 경우라면 반환 값이 맞지만,
그렇지 않는 경우에는 부모 노드의 발견 순서를 리턴하게 됩니다.
이 경우에는 역방향 간선으로 가는 정점이 아니라,
트리 간선으로 갈 수 있는 정점의 발견 시점이 되지 않을까요?
그래서 혹시 제가 생각해 본 함수의 반환값을 정의한 표현으로는,
[here를 루트로 하는 서브트리에서,
이 서브트리에 인접한 간선을 통해 갈 수 있는 정점 중에
가장 일찍 발견된 정점의 발견 시점을 반환한다]
라고 하면 소스 코드와 일치하지 않을까 싶습니다.
아직 많이 배우는 단계라
제 글에 틀린 점이 많을 수 있어서 확인해주시면 감사하겠습니다.
예를 들면, 그림 28.10에서, 루트가 0일때
호출된 findCutVertex(4)는, 실제로 3이라는 값을 리턴하지만,
역방향 간선이 존재하지 않으므로
함수 설명에 따르면 반환할 값이 없습니다.(모호해집니다)
위는 얼마 전에 올린 글입니다.
저 글을 올리게 된 것은, 무향 그래프에서도 '역방향 간선'이
방향 그래프와 같은 방법으로 정의된다고 생각했기 때문인데요,
다시 한번 잘 살펴보니, 무방향 그래프에서는
역방향 간선과 순방향 간선의 구분이 없다는 것을 알게 되었습니다.
그런데 또 위키피디아를 찾아보니, (back edge)
undirected graph에서는
모든 간선이 tree edge이거나 back edge 라고 설명이 되어 있어서요..
Signin
안녕하세요
JMBOOK 2권 856page 절단점 찾기 알고리즘을 공부하던 중에
궁금한 것이 있어서 질문드리게 되었습니다.
소스 코드 28.9에서 보면,
int findCutVertex() 함수 바로 위의 주석에서
[here를 루트로 하는 서브트리에서,
역방향 간선으로 갈 수 있는 정점 중에
가장 일찍 발견된 정점의 발견 시점을 반환한다]
라고 되어 있는데요,
소스 코드의 작동을 살펴보면,
실제 그 subtree가 부모 노드보다 더 일찍 발견된 노드와
[역방향 간선]으로 연결되어있는 경우라면 반환 값이 맞지만,
그렇지 않는 경우에는 부모 노드의 발견 순서를 리턴하게 됩니다.
이 경우에는 역방향 간선으로 가는 정점이 아니라,
트리 간선으로 갈 수 있는 정점의 발견 시점이 되지 않을까요?
그래서 혹시 제가 생각해 본 함수의 반환값을 정의한 표현으로는,
[here를 루트로 하는 서브트리에서,
이 서브트리에 인접한 간선을 통해 갈 수 있는 정점 중에
가장 일찍 발견된 정점의 발견 시점을 반환한다]
라고 하면 소스 코드와 일치하지 않을까 싶습니다.
아직 많이 배우는 단계라
제 글에 틀린 점이 많을 수 있어서 확인해주시면 감사하겠습니다.
예를 들면, 그림 28.10에서, 루트가 0일때
호출된 findCutVertex(4)는, 실제로 3이라는 값을 리턴하지만,
역방향 간선이 존재하지 않으므로
함수 설명에 따르면 반환할 값이 없습니다.(모호해집니다)
위는 얼마 전에 올린 글입니다.
저 글을 올리게 된 것은, 무향 그래프에서도 '역방향 간선'이
방향 그래프와 같은 방법으로 정의된다고 생각했기 때문인데요,
다시 한번 잘 살펴보니, 무방향 그래프에서는
역방향 간선과 순방향 간선의 구분이 없다는 것을 알게 되었습니다.
그런데 또 위키피디아를 찾아보니, (back edge)
undirected graph에서는
모든 간선이 tree edge이거나 back edge 라고 설명이 되어 있어서요..
어떻게 이해해야 할 지 잘 모르겠어서 질문드리게 되었습니다.
알려주시면 감사하겠습니다~!
10년 전