작성한 질문수 10

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 문을 실행하지 않습니다.

더 자세한 내용이나 다른 질문이 있다면 언제든지 물어보세요. 좋은 하루 되세요!