3-1.5 Algorithm 2회차 수업내용 정리

<Topological sort>

 

사이클이 없는 방향 그래프(DAG) 에서 정점을 일렬로 정렬

 

1. 순방향 방법 : 진입 차수가 0인 정점으로부터 출력하고 제거 

 

 

2. 역방향 방법 : 진출 차수가 0인 정점으로부터 출력하고, 그 출력된 그래프를 역순으로 -> 결국에 순방향 방법과 위상은 똑같이

 

 

Big O : O( N + M )

 

<Biconnected Component>

 

무방향 그래프의 연결 성분에서, 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분

-> 정점 하나가 삭제되더라도 또 다른 경로로 우회 가능 할 수 있게끔 

 

단절 정점 ( Articulation Point, Cut Point ) : 연결 성분의 정점 중 하나의 정점을 삭제했을 때, 두 개 이상의 연결 성분으로 분리될 떄 삭제된 정점.

 

다리 간선 ( Bridge ) : 간선을 제거했을 때, 두 개 이상의 연결 성분으로 분리 -> 이때의 제거 간선 

 

이때, Bridge는 Biconnected Component 의 조건에 부합하지 않지만, 그래프의 연결성을 결정짓는 중요한 요소이기 때문에 다리 간선도 특수한 형태의 이중 연결 성분으로 간주한다. 

 

ㅁ