목록2025/05/22 (1)
Elevation
그래프 (7) - 단절점과 단절선
그래프 간선의 분류단절점/단절선 알고리즘의 원활한 이해를 위해 그래프 간선을 분류하는 방법에 대해 알아보자. 유향 그래프에서, dfs를 하여 dfs 스패닝 트리가 형성되면 해당 트리를 기준으로 간선은 4가지로 분류할 수 있다.tree edge: dfs 트리에 속하는 간선forward edge: 조상에서 자손으로 향하지만, tree edge는 아닌 간선backward edge: 자손에서 조상으로 향하는 간선cross edge: 서로 조상-자손 관계가 아닌 두 정점 간 간선 무향 그래프의 경우, 방문하지 않은 정점을 연결하는 간선이 존재한다면 그 간선을 탐색할 것이므로 cross edge는 존재할 수 없다. 또한 방향이 없어 forward edge와 backward edge의 구분이 사라진다. 따라서 tre..
ps/graph
2025. 5. 22. 15:49