DNF LOVE

[자료구조 - 그래프의 주기] 방향 그래프와 무방향 그래프(SCC, BCC의 개념) 본문

Computer Science/자료구조

[자료구조 - 그래프의 주기] 방향 그래프와 무방향 그래프(SCC, BCC의 개념)

botho 2019. 9. 20. 19:20
반응형

1. SCC(Strogly connected component) - 방향 그래프의 순환

  • 단방향 그래프의 서로 다른 두 노드 U, V쌍에 대해 U -> V에 대한 경로가 존재하고, 동시에  V -> U에 대한 경로가 존재한다면 두 노드를 같은 SCC에 속한다고 정의한다.

2. BCC(Bi-connected component) - 무방향 그래프의 순환

  • 무방향 그래프의 서로 다른 두 노드 U, V쌍에 대하여 단결점 없는 경로가 존재하는 경우 두 노드를 같은 BCC에 속한다고 정의한다.

반응형