기말준비-그래프(Graph)

G=(V, E) | V는 정점(Vertice), E는 간선(=Edges)

Node a, Node b = Vertice // line(a,b) = Edge

 

G`=(V`, E`)에서 (V`,E`)가 (V, E)에 포함되면 이것은 G(V, E)의 subGraph(부분 그래프)이다.

Edge에 방향이 없다면 : 무향 그래프 (Undirected Graph)

Edge에 방향이 있다면 : 유향 그래프 (Directed Graph, =Di Graph)

Edge에 Weight가 있다면 : 가중치 그래프 (Weighted Graph)

정점 B가 정점 A에 인접해 있다면 : 인접 정점 (Adjacent Vertex)

정점 B의 인접 정점의 수 : 차수 (Degree), 방향이 있는 경우 in-degree / out-degree

순환(Cycle)이 없는 경로(Acyclic) : 단순 경로 (Simple Path)

 

| | 기호 : 개수를 의미 ( |V| = 정점의 개수 )

 

 

1. 인접 행렬

 |V| = n 일때, n개의 정점이 n개에 연결될 경우의 수 : n*n 이므로, 인접행렬은 n*n 크기의 행렬이다.

무향 그래프는 행렬이 위와 같이 대칭성을 갖는다.

 => 유향 그래프는 방향에 따라 1이 0이되기 때문에, 대칭성이 사라진다.

 

 

2. 그래프 탐색

 전체를 빠짐없이 탐색해야 하며, 이미 검색한 정점을 한번 더 검색하면 안된다. (중복 X, 누락 X)

 

 2-1) 깊이 우선 탐색 (DFS : Depth-First Search) (Stack 형식)

  연결을 따라서 진행하다가, 길이 막힌 경우 이전 갈림길로 돌아와서 다른 갈림길로 진행함. (Back Tracking)

  a에서 시작한 경우 a->b->c로 진행, c에서 갈곳이 없으므로 b->e->f, f에서 갈곳이 없으므로 a->d 검색완료.

 

 2-2) 너비 우선 탐색 (BFS : Breadth-First Search) (Queue 형식)

  각 정점의 인접 정점을 차례로 방문

  위의 그림에서 [NULL | {a}] → [a | {b, d}] → [b | {d, c, e}] → [d | {c, e}] → [c | {e}] → [e | {f}] → [f | {}] 로 진행

 

 

 3. 신장 트리 (Spanning Tree)

  G=(V, E)는 모두 연결되어 있어야함.

  subGraph T=(V, E`)가 G의 신장 트리이기 위해서는 그래프의 모든 정점을 갖고, 모든 정점이 연결, 비순환되어야 한다.

  또한, E`는 E에 포함되어 있어야한다.

   -> DFS나 BFS를 사용해 검색하는 과정에서 만들어진 트리도 신장트리이다.

 

 

4. 최소 비용 신장 트리 (Minimum Spanning Tree, MST)

 트리 -> |V| = |E| + 1

 그래프는 모두 연결되어 있으며, Weight를 갖고 있다.

 Edge의 개수는 |V|-1(가장 적은 연결) ~ |V|*(|V|-1)/2(가장 많은 연결)

 M = (V, E`) : G(V, E)의 MST [ G의 신장 트리 중, Edge Weight의 합이 최소가 되는 신장트리 ]

 

 4-1) Kruskal's Algorithm

  - Greedy 알고리즘, 순환을 만들지 않는 최소 Weight의 Edge들을 차례로 추가하여 구성한다.

  - Edge를 Weight 순서로 정렬한 뒤, |E|가 |V|-1가 될 때 까지, 계속 정렬된 순서대로 로드한다.

  - 불러온 Edge가 순환을 만든다면 삭제한다.

  - 이렇게 만들어 진 그래프(V, E`)는 MST가 된다.  // O (|E| lg|E|)

 

 4-2) Prim's Algorithm

  - Greedy 알고리즘, 정점을 추가할 때 최소 Weight의 Edge를 선택한다.

  - 빈 그래프에, 본 그래프의 정점을 하나 복사해서 가져온다.

  - 가져온 정점에 이어진 Edge중 가장 Weight가 낮은 Edge를 연결된 정점과 함께 가져온다. 이것을 반복

  - 이렇게 만들어 진 그래프(V, E`)는 MST가 된다.  // O (|E|^2)

 

* 그래프가 Sparse (|E| 가 |V|-1에 가까움) 일 수록, Kruskal's Algorithm이 유리함.

  그래프가 Dense (|E| 가 |V|*(|V|-1)/2에 가까움) 일 수록, Prim's Algorithm이 유리함.

 

4-3) Union-Find 자료 구조 (Disjoint set Algorithm) : 순환 여부 확인을 위한 자료 구조

  - n개의 seperated set이 주어진다.

  - V1~Vn을 생성한다. 이 정점들은 각각 자기 자신을 root로 하고 있는 트리이다.

  - 자료 트리에서 선택된 데이터의 root를 찾는다. 이 때, 가는 길에 거친 정점들은 모두 root를 가리킨다. (경로 압축)

 

 

 

 5. 최단 경로 (Shortest Path, SP)

  Weight가 존재하며, 모든 Weight가 0을 넘는 그래프

  V0에서 Vk로 갈때의 경로는 <V0, V1, V2..., Vk>로 표시한다. ( Path )

  W(P) 는 해당 Path에서의 Weight의 합을 의미한다.

u에서 v로 가는 Path위에 그냥 Path면 P, 최단 경로면 SP를 표기한다.

 

 5-1) SP Problems

  SPSP ( Single Pair SP )

     : 한 출발지에서 한 목적지로 가는 최단 경로

  SSSP ( Single Source SP ), SDSP ( Single Destination SP )

     : 한 출발지->모든 목적지 or 모든 출발지->한 목적지만 정해진 최단 경로

  APSP ( All Pairs SP )

     : 모든 출발지에서 모든 목적지로 향하는 최단 경로

 

 W[i][j] : Vi에서 Vj로 갈때 Edge의 가중치 행렬, Vi = Vj라면 가중치는 0, Edge가 없다면 무한이다.

 D[i] : 출발점 V0으로 부터 각 정점 까지의 최단 거리

 Path[i] : 출발점 V0이 root인 SP Tree로서, 각 정점의 부모 노드를 저장

그래프와 Path[i]

 

 5-2) Dijkstra Algorithm ( SSSP 문제 해결, O(N^2) )

  Single Source V0으로 부터 각 정점까지의 최단 거리를 구한다. D[x]

  실제 최단 경로는 V0을 root로 하는 SP Tree를 구성하여 해결한다.

 

 - 1. S = {V0} // 출발지점 등록

 - 2. D[n] = W[V0] // V0으로 부터 거리를 V[0]의 인접정점 거리로 초기화

 - 3. u = D[V0]에서 가장 가까운 정점, u를 S에 추가한다.

 - 4. u에 인접하면서 S에 포함되지 않은 인접 정점에 대하여 거리 유효성 테스트를 한다.

 - 5. 거리 유효성 테스트 : V0->Z가 V0->u->Z보다 빠른지 늦는지를 확인한 후 짧은 쪽 사용

        D[Z] = min(D[Z], D[u]+W[u][z])

 - 6. S 배열에 정점 모두가 들어갈 때 까지 3~5를 반복함.

 

 5-3) Floyd Algorithm ( APAP 문제 해결, O(N^3) )

  Dijkstra Algorithm을 N번 반복하는 것보다 간단함.

  W[n][n] : 그래프의 가중치 행렬

  A[n][n] : 정점 간 거리 행렬

  A[i] : Vi에서 부터의 최단 거리

  Ak[i][j] : k단계 Vi에서 Vj로 가는 최단 거리

 An-1[i][j] : 지나가는 정점의 제한 없이 i에서 j로 가는 최단 거리