절단점 찾기 알고리즘에 대해서 물어봅니다.

  • dookim123
    dookim123

    dfs스패닝트리에서 절다점 찾기시에 선조노드로 가는 역방향간선을
    찾는다고 하는데, 애초에 트리에 교차간선이나 역방향 간선은 없지 않나요 ?


    9년 전
2개의 댓글이 있습니다.
  • wookayin
    wookayin

    DFS tree는 directed tree 입니다.

    http://en.wikipedia.org/wiki/Depth-first_search#/media/File:Tree_edges.svg

    위키피디아 그림이 도움이 되곘네요.


    9년 전 link
  • JongMan
    JongMan

    트리에 대해 dfs를 수행하면 그 결과로 얻어지는 dfs 스패닝 트리에는 역방향이나 교차 간선이 없습니다. ^^; 일반적인 그래프에 대해 dfs를 수행하면 역방향이나 교차 간선이 생기겠죠.


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