무향 그래프에서의 back edge의 정의

  • Signin
    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 라고 설명이 되어 있어서요..

    어떻게 이해해야 할 지 잘 모르겠어서 질문드리게 되었습니다.
    알려주시면 감사하겠습니다~!


    11년 전
6개의 댓글이 있습니다.
  • KimJJ
    KimJJ

    Back edges in this case are the edges connected to vertices that you already visited in DFS traverse.


    11년 전 link
  • KimJJ
    KimJJ

    I'm sorry about English I wrote these on an android phone and I can't type Korean correctly maybe bug of firefox..


    11년 전 link
  • Signin
    Signin

    음.,.. 그럼 무향 그래프에서 (a,b)가 트리 간선이면
    (b,a)를 역방향 간선으로 생각한다는 말씀이신가요~?
    아니면, 이 둘은 같은 간선이니 트리 간선만 해당되는 건가요?


    11년 전 link
  • Signin
    Signin

    댓글 달아주셔서 감사합니다 ㅠㅠ


    11년 전 link
  • Kureyo
    Kureyo

    a
    |
    b
    |
    c
    형태로 dfs tree를 탐색했는데 (a,c)간선이 존재하면 역방향 간선입니다


    11년 전 link
  • Signin
    Signin

    감사합니다~!


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.