그래프이론 알고리즘/자료구조

그래프 이론의 필요성

  높은 수준의 프로그래밍을 하기 위해서는 그래프이론에 대한 탄탄한 이해가 필수적이다. 프로그래밍의 발전은 결국 정보의 연결성의 증대에 의한, 연결성 증대를 위한 방향으로 발전하고 있기 때문이다. 예를 들어, FaceBook과 같은 연결형 SNS, Google과 같은 검색엔진, Netflix와 같은 추천서비스, Amazon과 같은 동선최적화, OpenAI와 같은 자연어처리 등 모두 내가 선택한 Node로부터 주변 Node를 탐색하는 문제이기때문이다. 

  고등수학에서 잘 다루지 않아서 익숙하지 않은 것이지 어려운 것은 아니라고 생각한다. 높은 수준의 프로그래머가 되기 위해서는 결국엔 선형대수학을 어느정도는 이해해야 할 것이고 그것의 근본이 그래프 이론이니 지금부터 피할 수 없는 기초를 쌓아나간다고 생각하고 조금씩 정진해 나가자. 오히려 기회다.

그래프 이론 (Edge and Vertex)

그래프 자료구조

• 연결되어 있는 원소들간의 관계를 표현하는 자료구조이다. 그래프는 G(V, E)로 정의하고, V(Vertext : 정점)과 E(Edge : 간선) 의 집합을 의미한다.
• 보통 시작하는 Vertex로부터 이웃한 Vertex를 표현하는 Adjacency(인접)이라는 개념으로 표현한다.
  • *인접리스트 : 각 리스트의 index가 탐색을 시작하는 Vertex를 의미하는 리스트이며 각 index의 데이터는 이웃하는 Vertext를 의미 for each vertex u ∈V, Adj[u] stores u’s neighbors, i.e., {v ∈V |(u, v) ∈E}.
  • 인접행렬 : 인접리스트를 2차원 배열을 이용해 표현하는 방법. 
  • 인접함수 :Adj(u) is a function — compute local structure on the fly
  • Object-oriented 인접함수 : object for each vertex u, u.neighbors = list of neighbors i.e. Adj[u]

Comparision Model and Decision Tree

• In this model, comparable objects can be thought of as black boxes, supporting only a set of binary boolean operations called comparisons (namely <, ≤, >, ≥, =, and !=).Each operation takes as input two objects and outputs a Boolean value, either True or False, depending on the relative ordering of the elements.
• Binary Search
  • There must be a leaf for each possible output to the algorithm. the worst-case number of comparisons that must be made by any comparison search algorithm will be the height of the algorithm’s decision tree which is Log n

 

DFS (Depth First Search)

• recursively explore and backtrack along breadcrumbs until reach unexplored neighbor. careful not to repeat a vertex. 탐색가능한 경로 중 더이상 탐색이 불가할 때까지 순차적으로 탐색하는 방법.

Adjacency list로 정의된 DFS

시작점을 Index로 하여 adj list를 조회를 통해 neighbor을 확인하고 s를 neighbor의 parents로 저장함.  neighbor의 Parent가 등록여부를 확인하여 Visited Vertex인지 확인하는 구조. BFS와는 달리, adj를 조회하는 시점에서 재귀함수를 호출하여 stack구조로 조회를 확장시켜나감

 

def dfs(Adj, s, parent = None, order = None): # Adj: adjacency list, s: start

2 if parent is None: # O(1) initialize parent list

3 parent = [None for v in Adj] # O(V) (use hash if unlabeled)

4 parent[s] = s # O(1) root

5 order = [] # O(1) initialize order array

6 for v in Adj[s]: # O(Adj[s]) loop over neighbors

7 if parent[v] is None: # O(1) parent not yet assigned

8 parent[v] = s # O(1) assign parent

9 dfs(Adj, v, parent, order) # Recursive call

10 order.append(s) # O(1) amortized

11 return parent, order

 

 

 BFS Breadth First Search 

• Explore graph level by level from s
• build level i > 0 from level i−1 by trying all outgoing edges, but ignoring vertices from previous levels.
• BFS는 최단거리를 손쉽게 찾아낼 수 있다. 반면 DFS는 전수 탐색을 마쳐야만 최단거리를 비교를 통해서 찾아낼 수 있음.
• BFS 문제풀이 특징
  1. 횟수라는 단어가 들어간다면 BFS탐색 문제이다
  2. 갔던 경로는 다시 방문하지 않도록 int[] chk를 활용해서 

Adjacency list로 정의된 BFS

• 시작점을 level 0으로 저장함. 그 후 시작점을 Index로 하여 adj list를 조회를 통해 neighbor을 확인하고 이를 next level로 저장함.  edge in level을 통해서 visited vertex인지 확인하는 구조. DFS와는 달리 level을 모두 조회 후 level = next level로 assignment 하는 반복 구조로 조회를 확장함.

1 def bfs(Adj, s): # Adj: adjacency list, s: starting vertex

2 parent = [None for v in Adj] # O(V) (use hash if unlabeled)

3 parent[s] = s # O(1) root

4 level = [[s]] # O(1) initialize levels

5 while 0 < len(level[-1]): # O(?) last level contains vertices

6 level.append([]) # O(1) amortized, make new level

7 for u in level[-2]: # O(?) loop over last full level

8 for v in Adj[u]: # O(Adj[u]) loop over neighbors

9 if parent[v] is None: # O(1) parent not yet assigned

10 parent[v] = u # O(1) assign parent from level[-2]

11 level[-1].append(v) # O(1) amortized, add to border

12 return parent

How fast is breadth-first s