인프런 커뮤니티 질문&답변
작성한 질문수
Dfs 함수의 순방향 간선 예외 체크 로직에 대해 여쭤봅니다.
작성
·
318
0
Dfs 함수에서
if(_discoveredOrder[here] < _discoveredOrder[there]) contiue;
해당 로직을 통해서 순방향 간선이면 continue를 하여 넘어갔는데 해당 if 문에 걸리는 경우가 존재하나요??
_discoveredOrder[there]의 값이 -1이 아니라는 뜻은 자신의 부모로부터 이미 방문한 적이 있다는 뜻인데 if 문에 걸리는 것이 없는 것 같아서요.
어떤 경우에 발생하는 지 궁금합니다.
답변 2
0
1년 지난 질문이지만 제가 답변해보겠습니다.
순방향 간선의 존재는 그래프를 그려보면 어렵지 않게 찾을 수 있긴 해요. DFS 스패닝 트리가 만들어졌을 때 0 -> 1 -> 5 경로가 트리 간선일 경우, 0 -> 5가 존재하는 간선이 순방향 간선이에요. 즉 순방향 간선은 트리 간선에 포함되지 않는 간선입니다.
순방향 간선은 조상에서 자손으로 가는 일종의 지름길 역할을 하기 때문에, 이미 방문한 노드 간에 발생합니다. 때문에 _discoveredOrder[there]가 != -1인 경우에 생겨요. _discoveredOrder[there]가 == -1인 경우는 트리 간선이에요.
트리 간선(dfs 스패닝 트리), 순방향 간선, 역방향 간선, 교차 간선에 대해 다시 한 번 개념을 잡아보세요🙂
0
안녕하세요, 인프런 AI 인턴이에요.
if(_discoveredOrder[here] < _discoveredOrder[there]) continue; 해당 로직은 DFS(Depth-First Search) 알고리즘에서 순방향 간선을 처리하기 위한 예외 체크 로직입니다.
여기서 _discoveredOrder[here]는 현재 정점(here)의 방문 순서, _discoveredOrder[there]는 순방향 간선으로 연결된 정점(there)의 방문 순서를 나타냅니다.
_discoveredOrder 배열은 초기 값이 -1로 설정되어 있으면서, 각 정점이 방문되는 순서대로 값이 갱신됩니다. 따라서 _discoveredOrder[there] 값이 -1이 아니라는 것은 정점 there이 이미 방문되었다는 의미입니다.
순방향 간선은 정점 here에서 정점 there으로 이어지는 간선이지만, 정점 there이 이미 방문된 상태라면 이 간선은 순환 구조를 형성하게 되며, 따라서 이 간선은 무시해야 합니다. 그래서 if(_discoveredOrder[here] < _discoveredOrder[there]) continue; 코드에서는 이러한 순환 구조를 방지하기 위해 continue 문을 사용하여 다음 간선으로 넘어가도록 처리하고 있습니다.
따라서, 순방향 간선인데 해당 if 문에 걸리는 경우는 발생하지 않으며, 이 경우에는 continue 문을 실행하지 않습니다.
더 자세한 내용이나 다른 질문이 있다면 언제든지 물어보세요. 좋은 하루 되세요!