책의 오일러서킷 찾아내는 알고리즘(28장)에 관한 질문입니다

  • catniz
    catniz

    책 2권 841쪽의 코드28.4 에서

    getEulerCircuit 함수안에 circuit.push_back(here) 를 함수의 맨 끝에 적으셨더라고요. 그렇게 정점을 모두 저장하고 유향그래프의 경우 맨 뒤에서부터 출력을 한다고요.

    근데 저 push_back을 맨 뒤가 아니라 맨 앞에 쓰는 것은 왜 안되는지 궁금합니다. 만약 된다면 그냥 저장한 뒤 순서를 뒤집을 필요없이 출력할 수 있지 않나요?


    10년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    아래와 같은 그래프를 생각해 봅시다.

    • a - b - c - d 경로가 있고
    • b를 포함하는 사이클 b - e - f - b 가 있습니다.

    이 때 처음 dfs를 해서 a - b - c - d경로를 따라갔다고 하죠. 돌아오는 과정에서 간선 b - e 를 발견하고, b - e - f - b를 따라갔다가 돌아오게 됩니다. 따라서 정점들을 발견하는 순서는 a, b, c, d, e, f, b입니다. 이건 경로가 아니죠. d와 e 사이에는 간선이 없기 때문입니다. 반면 반환하는 순서는 d, c, b, f, e, b, a로 우리가 원하는 오일러 트레일이 되지요.

    설명이 좀 부족한데, 이해가 안가시면 이 그래프에 대해 한번 직접 짜서 돌려보세요. ^^;


    10년 전 link

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