컴퓨터알고리즘#16

LeeMir, 19 May 2021

방향 그래프

모든 간선이 방향 간선인 그래프
간선 (a, b)는 a에서 b로 가지만, b에서 a로 가지는 않음
진입 간선들과 진출 간선들을 각각 별도의 인접 리스트로 보관한다면, 진입 간선들의 집합과 진출 간선들의 집합을 각각 크기에 비례한 시간에 조사 가능
방향 DFS
- 간선들을 주어진 방향만을 따라 순회하도록 하면, DFS 및 BFS 순회 알고리즘들을 방향 그래프에 특화 가능
- 방향 DFS / BFS 알고리즘에서, 네 종류의 간선이 발생
  - 트리간선 / 후향간선 / 전향간선 / 교차간선
도달 가능성
- 그래프 G에 u에서 v로의 방향 경로가 존재한다면, u는 v에 도달한다라고 표현
강연결성
- 그래프 G의 어느 두 정점 u와 v에 대해서나 u는 v에 도달하며 v는 u에 도달하면 G를 강연결이라고 말함
- 강연결 검사
  - G에서 DFS 수행, G를 역행한 G’에서 DFS 수행해서 모든 정점을 다 방문하는 지 검사
- 강연결 요소
  - 방향 그래프에서 각 정점으로부터 다른 모든 정점으로 도달할 수 있는 최대의 부그래프
이행적폐쇄
- A에서 B로 갈 수 있고, B에서 C로 갈 수 있다면 A에서 C로 가는 경로를 추가
  - Floyd-Warshall 알고리즘