알고리즘

[알고리즘 #6] 그래프 이론

우당탕탕코딩일기 2023. 4. 6. 11:27

 

Graph 기초

: Graph G는 vertex의 집합 V(G)와 두 vertex의 pair 인 edge들의 집합 E(G)로 구성되어 있는 구조이다. G=(V(G), E(G)) 로 표기한다.

 

  • Directed Graph

E(G)의 각 원소들은 ordered pair임( 방향성이 있음 )

  • Undirected Graph

E(G)의 각 원소들은 unordered pair임( 방향성이 없음 )

 

 

- adjacent 

(u,v) E E(G) 일때 U, V는 adjacent 하다고 한다. 

 

- Degree of u (deg(u)) 

G에서 vertex u와 adjacent 한 vertex 수이다.

 

- Edga (u,v) 가 있는 경우 v는 u의 neighbor 이다.

 

- Directed graph 의 경우 in-degree 와 out-degree를 따로 정의할 수 있다. 

 ( 그 vertex 기준 들어오는 화살표를 in-degree 나가는 화살표를 out-degree라고 한다)

 

 

- Connectivity

(Undirected) Graph G 에서 G = (V(G), E(G)) 에서 

- G 는 connected 히다 : 임의의 서로 다른 두 vertex v, w E V(G) 에 대해 v에서 w로의 path 가 존재한다. 이 떄 G를 connected Graph 라고 한다. 

- connected 하지 않은 그래프는 disconnected라고 한다. 

 

 

그래프 저장 방법

  • Adjacency matrix
  • Adfacency list

 

Adjacency matrix

Vertex n개인 Graph G를 nxn  matrix(array) 를 이용하여 저장

Weighted graph 일 경우, array 의 각 (i, j) 번째 entry 에 edge( I, j) 의 weight 를 저장한다. 

 

 

(* github 구현 *)

 

Adfacency list

Vector의 array로 쉽게 구현 가능하다.

Weighted Graph 인 경우, 각각의 구성 요소가 pair 인 vector v의 list로 관리할 수 있으며, 이 경우 v[i] 가 pair(j, b) 를 포함하는 것은 edge (i, j) 의 weight 가 b임을 나타냄

 

(* github 구현 *)

 

 

  Adjacency Matrix Adjacenc List
Space O(n^2)  O(n+m)
Vertex u와 v가 adjacent 한지 체크 O(1) O(deg(u))
Vertex u와 adjacent한 모든 vertex 탐색 O(n) O(deg(u))
deg(u) 답하기 O(n) O(deg(u))

 

Graph Traversal

DFS(Depth-First Search) : 시작 vertex 에서 시작하여 해당 vertex에서 reachable(도달 가능한) vertex를 recursive하게 방문하는 방법

이미 방문한 vertex 를 재방문하지 않기 위해 visited 라 하는 array 로 이미 방문한 vertex 의 목록을 관리한다.

Adjacency list 를 사용할 경우 O(n+m)이다. ( matrix 는 O(n^2))

Time Complexity
1. List 사용시 : O(m+n)   2. Array 사용시 : O(n^2)

(* github 구현 *)

 

BFS(Breadth-Fisrt Search) :  임의의 시작 vertex에서 시작하여 해당 vertex와 거리(= 두 vertex간의 path에 존재하는 edge 수) 가 가까운 순서대로 방문하는 방법  

  • 기준점에서 거리가 가까운 순서대로 방문
  • 트리로 나타낼 수 있다
  • 다음에 방문할 vertex를 큐로 관리한다.
  • Unweighted Shortest Path 구할 때는 BFS 사용 하는 것이 유리하고, 그 외 보통은 DFS를 주로 사용한다.
Time Complexity
1. List 사용시 : O(m+n)   2. Array 사용시 : O(n^2)

(* github 구현 *)

 

 

Graph Traversal 응용

* maximal : 더이상 추가가 안된다는 것 / 더이상 vertex 추가할 수 없을 

* maximum : 포함 관계에 따라 최대인/ 극대의  / Maximum인 것은 maximal이기도 하다.

 

1. Connectivity Check

  • reachable 하지 않다면 path 없다. connected 하지 않다.
  • 아무 vertex 로부터 traversal 을 시작해서 한번에 graph 의 모든 vertex를 방문할 경우 connected 위 과정을 반복함으로써 graph의 모든 connected componen 를 반환할 수 있다. 

(* github 구현 *)

 

 

2. Cycle Check

  • DFS 트리에서 어떤 vertex V와 adjacent 하는 애들 중에서, adjacent 한데 방문을 이미 한 vertex들이 있으면 , cylcle 이 생긴다. 
  • 트리에서는 항상 [V] - 1 = [E] 이다. (*증명: 트리의 리프들은 연결된 edge가 항상 한 개이다. 만약 리프는 제거하더라도 여전히 트리이다. vertex 개수가 k+1 개인 그래프를 생각해보자. edge는 k개 인가? // vertex 개수를 n이라고 가정하자 Base case) n=1 이면, 선의 개수는 0개이다. (성립) n=k 일때 참이라고 가정하자. / vertex가 k+1 개인 임의의 그래프 T를 잡았을 때, 이 그래프는 vertex가 두 개이상이므로 리프가 존재한다. 여기서 리프 v를 제거하고 난 그래프 T' 을 가정했을 때, vertex는 k개이다. n=k일 때 성립함을 가정했으므로 edge는 k-1개이다. T 기준 제거한 v가 리프노드였기 때문에 연결된 edge는 한 개이다. 따라서 T에서의 edge개수는 T'의 edge개수에서 한 개를 더한 것이 된다. 따라서 수학적 증명법에 의해, vertex가 n+1 개인 나무는 n개의 edge를 갖는다 ) 
  • 트리의 성질 이용하면 vertex 가 c개인 connected component 에 대해 edge가 c-1 개보다 많다면 무조건 cycle 이 존재하낟.

(* github 구현 *)

 

 

3. Bipartiteness Check

  • 두 개의 partition을 지정하여 vertex set을 partitioning 할 수 있는 경우 같은 색깔로 칠해진 두 vertex 사이에 edge가 없도록 색칠이 가능한 경우, 해당 그래프는 Bipartite graph 이다.
  • 내가 현재 빨간색이면 이웃한 인접한 애는 파란색으로 칠하고 이런식으로 돌면서 체크한다. 다음에 순회할 때 만약 red 와 red 사이 back edge 있다면 이 그래프는 bipartite grapch 가 아니다. 충돌안생기면서 끝까지 체크할 수 있다면 bipartite grapch 이다. 
  • bipartite graph 가 아니다 = odd cycle(길이가 odd인 cycle) 이 있다는 사실과 equvalent 함. 

(* github 구현 *)

 

 

ex) Uva 11953 Battleships

nxn 바둑판 형식의 그리드가 주어진다. battleship 은 horizontal 하게 있거나 vertical 하게 존재한다. 번갈아 가면서도 가능하다. 그러나 대각선으로는 안된다. 각 배틀십은 고유한 공간을 차지하고 있다. 배틀십 개수를 구하여라

입력 : 테이스 케이스 T 입력 -> N(그리드 사이즈) 입력 -> N개의 캐릭터들 각각은 플레잉 중인 그리드를 묘사한다. '.'이면 비어있는 셀이고 'x'이면 쉽을 포함하거나 그것의 부분을 포함한다. '@'은 이미 쉽이 친 부분이다.

 

=> 연속된 x와 @로 이루어진 path 그래프 이다. x로만 이루어진 path 찾아야한다.

 

Flood Fill기법 사용(방문한 모든 cell 들을 덧칠하여 시간과 공간을 절약할 수 있다)

-> DFS 돌면서 'x' 발견할때만 dfs 하면 된다. 'x' 로 connected 된 덩어리들의 개수가 정답이므로 첫 dfs 실행될때 res 값을 ++ 해준다. DFS 로 방문할때 방문한 모든 vertex를 '.'으로 업뎃하여 다음엔 방문 안하도록한다. 

 

(* github 구현 *)

 

 

 

 

Shortest Path

 

1. Unweighted case : BFS 이용

(* github 구현 *)

 

 

2. Weighted case

- Weight 가 모두 non-negative 일 때 - O((n+m)log n) , Dijkstra

-> 보통 많이 사용한다. single source shortest path

 

- Negative cycle 이 존재하지 않을 때 - O(nm) , Bellman-Ford

-> Negative Cycle 일때이고 single source shortest path

 

- Negative cycle 이 존재하지 않을 때 - O(n^3) , Floyd-Warshall

  -> 임의의 두 점간의 shortest parh 구할 수 있다.(All-pairs shortest path) 입력값작은 경우 주로 사용되고 실전에서 은근 많이 사용된다. 

 

 

Dijkstra 

  • 내가 방문안한애들중에 가장 shortest 한애를 다음 vertex 로 계속 update 해 나가는 greedy Algorithm 이다. 
  • 아직 처리하지 않은 vertex 들 중  source 로부터 길이가 가장 짧은 vertex는 실제 shortest path 의 길이와 일치한다는 사실을 이용한다.( negative weight 인 edge 존재할 때는 성립안한다.)
  • 각 element 가 source 에서 x까지 shortest path 의 길이의 pair 로 구성된 priority queue 를 이용하면 O((n+m)log m) 시간에 구현이 가능하다.
  • C++ 의 경우 priority 성질로 인해 -1 곱한 값을 저장해야한다. (* C++ priority queue는 자동으로 내림차순이기 떄문)

 

(* github 구현 *)

 

다익스트라 negative edge있을때 성립하지 않는 이유 : 현재 방문하지 않은 노드 중 가장 짧은게 shortest path인데 노드 u에서 v로 가는데 weight 를 w라고 놓자. 만약 u와 v사이에 노드 m이 있고 e(u, m) 의 weight를 w1, e(m,v) 의 weight 는 negative 이며 이를  n이라고 하자. w1>w 이면서 w1-n < w 일때 다익스트라 알고리즘은 그리디하게 w를 택하여 v로 도착할 것이다. 그러나 실제로는 w1-n < w 이므로 negative edge를 거쳐서 가는 것이 더 shortest path 이다 따라서 negative edge 있다면 shortest path를 보장하지 않는다. 

 

Bellman-Ford

  • DP 기반 shortest path Algorithm
  • dist(i, u) 라는 함수를 정의한다. i번째 round 까지 끝난 뒤에 시작점에서 u까지의 shortest path 이다. i번째  round 는 edge를 i개 이하로 사용하는 sorce 에서 각 vertext간의 shortest path의 길이로 정의된다.
  • 모든 case 탐색하므로 느리다.
  • dist(i, u) = min(dist(i-1, u), min(dist(i-1, u' ) + w(u', u))
  • negative cycle 있으면 길이가 한없이 줄어들어서 동작하지 않는다. ( *증명*) -> 한없이 줄어드는 게 있다면 해당 graph는 negative cycle 가진다고 판별할 수 있다.

 

(* github 구현 *)

 

+ Bellman-Ford 복습

v0 -> v1 -> v2 -> .. -> vk가 s에서 도달할 수 있는 negative cycle 이라고 가정하자. 여기서 v0 = vk이다. 포말하게 이것은 우리 (i=1부터 k까지)∑ w(v_i-1, v_i) < 0 임을 의미한다. contradiction 으로 진행하면 우리가 모든 i = 1, . . . , k.에 대해  dn−1(vi) ≤ dn−1(vi−1) + w(vi−1, vi) 일때 사이클에서 각각의 vertex에대해 부등식을 더하면

( 모든 시그마 i=1부터 k까지) ∑ dn−1(vi) ≤∑ dn−1(vi-1) + ∑w(vi−1, vi) 이다

v0 = vk 이기 때문에 

 (i=1부터 k까지) ∑ dn−1(vi-1) =  (i=0부터 k-1까지)∑dn−1(vi) = dn−1(v0) + (i=1부터 k-1까지)∑dn−1(vi) = (i=1부터 k까지) dn−1(vi) 가 성립한다.

앞 두개가 같으므로 그것들을 cancel하면

(i=1부터 k까지) w(vi-1, v i) >= 0

모순이 발생하므로 가정 v0 -> v1 -> v2 -> .. -> vk 는 negative cycle 이다.

 

Floyd-Warshall

 

  • DP 기반으로 한다.
  • recurrence 를 다르게 정의한다. 시작점이 고정이 아니기 때문에 parameter 3개 필요하다. Vertext set V={1,2,..,n} 이라 할 때 i 번째 round 는 'vertex {1...i} 만을 중간지점으로 사용하는 all-pairs shortest path 의 길이를 저장한다.
  • dis(i, j, k) 가 k-th round 가 지난 이후 저장된 vertex i 에서 j 로의 shortest path 의 길이라 하면 다음 recurrence 성립한다 
  • dist(i, j, k) = min(dist (i, k , k-1) + dist (k, j, k-1), dist(i,j,k-1))
  • 2차원 array 사용하여 쉽게 구현할 수 있다.

 

(* github 구현 *)

 

 

ex) Uva 01056 - Degrees of Separation

 

(* github 구현 *)

 

728x90