방향그래프 개념

방향 그래프

모든 간선이 방향 간선인 그래프

속성과 구현

진입간선(in-edge)와 진출간선(out-edge)들을 별도의 부착리스트로 보관한다면 진입간선의 집합과 진출간선의 집합을 각각의 크기에 비례한 시간에 순회할 수 있다.

방향 DFS 간선(v,w)

• 트리간선 : w가 v의 자식이다.
• 후향간선 : w가 v의 조상이다.
• 전향간선 : w가 v의 자손이다.
• 교차간선 : w가 v와 동일하 레벨 또는 직계가 아닌 다음 레벨에 위치한다.

  강연결성

  정점 u와 v에서 서로 도달 가능하다면 강연결 그래프라고 한다.

  강연결 검사

1. G의 임의의 정점 v를 선택
2. G의 v로부터 DFS를 수행

• 방문되지 않은 정점 w가 있다면 False를 반환

3. G의 간선들을 모두 역행시킨 그래프 G'을 얻음
4. G'의 v로부터 DFS를 수행

• 방문되지 않은 정점 w가 있다면 False를 반환
• 그렇지 않으면 True를 반환
  두 번의 DFS를 수행하므로 O(m+n)시간 소요

  강연결요소

  각 정점으로부터 다른 모든 정점으로 도달할 수 있는 최대의 부 그래프

  이행적 패쇄

• G*는 G와 동일한 정점들로 구성된다.
• G에 u로부터 v != u로의 방향경로가 존재한다면, G에 u로부터 v로의 방향간선이 존재한다.
  즉 거쳐서 가는 길이 있다면 한번에 가는 길을 만들어 놓은 것이 G이다.

  Floyd-Warshall

  그래프의 각 정점에서 DFS를 수행한 결과를 종합하여 보여주므로 O(n(m+n))시간이 소요된다.

1. 정점들을 1,2,....n으로 번호를 매긴다.
2. 1,2,...,k로 번호 매겨진 정점들만 경유 정점으로 사용하는 경로들을 고려한다.

   Alg Floyd-Warshall(G)
   

1.Let v1,v2,...,vn be an arbitrary numbering of the vertices of G
2. G0 = G
3. for k = 1 to n
Gk = G(k-1)
for i = 1 to n, i != k
for j = 1 to n,j != i,k
if(G(k-1).areAdjacent(vi,vk) && G(k-1).areAdjacent(vk,vj))
if(!Gk.areAdjacemt(vi,vj))
Gk.insertDirectedEdge(vi,vj,k)
4. return Gn

## 동적 프로그래밍
- 부문제 단속성 : 부 문제들이 몇개의 기본 변수로 정의될 수 있음
- 부 문제 최적성: 전체 최적치가 최적의 부문제들에 의해 정의될 수 있음.
- 부 문제 중복성: 부 문제들이 독립적이 아니라 상호 겹쳐짐(따라서 해결을 "상향식"으로 구축할 필요가 있음)
### 공통점
문제공간 : 원점 - 목표점 구조
- 원점 : 문제의 초기 또는 기초 지점(복수 개수 가능)
- 목표점 : 최종해가 요구되는 지점(보통 1개)
- 추상적 개념 상의 두 지점
### 차이점
동적 프로그래밍 (단방향): 원점 -> 목표점
분할통치(양방향) : 목표점 -> 원점 -> 목표점
### 성능
- 동적 프로그래밍: 단방향 특성 때문에 종종 효율적
- 분할 통치: 분할 회수, 중복연산 수행 회수

## 방향 비 싸이클 그래프 DAG
싸이클식 참조가 없도록 정의된 그래프
### DAG와 위상 정렬
#### 위상 순서
모든 i<j인 간선(vi,vj)에 대해 정점들을 번호로 나열한 것
- 방향그래프가 DAG면 위상순서를 가지며 그 역도 참이다.  
#### 위상 정렬
DAG로부터 위상순서를 얻는 절차

Alg topologicalSort(G)

1. Q = empty queue

2. for each u to G.vertices()
   in(u) = inDegree(u)
   if(in(u)= 0)

    Q.enqueue(u)

3. i = 1

4. while(!Q.isEmpty()){
   u = Q.dequeue()
   Label u with topological number i
   i++
   for each e to G.outIncidentEdges(u){

    w = G.opposite(u,e)
    in(w) = in(w)-1
    if(in(w)= 0)
        Q.enqueue(W)

   }
   }

5. if (i <= n)
   write("G has a directed cycle")

6. return

7. 0인걸 큐에 다 넣기

8. 0에서 나가는 간선의 반대편 전부 1씩 빼주기

9. 빼줬을 때 0이면 큐에 넣기

10. 무한 반복

Alg topologicalSortDFS(G)

1. n = G.numVertices()
2. for each u to G.vertices()
    l(u) = Fresh
3. for each v to G.vertices(){
    if(l(v) = Fresh)
        rTopologicalSortDFS(G,v)
}


Alg rTopologicalSortDFS(G,v)

1. l(v)= Visited
2. for each e to G.outIncidentEdges(v){
    w = opposite(v,e)
    if(l(w) = Fresh)
        rTopologicalSortDFS(G,w)
    else if w is not labeled with a topological number
        write("G has a directed cycle")
    else
        e is a nontree edge
}
3. Label v with topological number b
4. n--

1. Fresh 면 계속 가
2. 갈 곳 없으면 라벨 붙여
3. 직전 정점으로 돌아가서 반복