파이썬 알고리즘 인터뷰 - 그래프

그래프

그래프

• 수학에서, 좀 더 구체적으로 그래프 이론에서 그래프란 객채의 일부 쌍들이 연관되어 있는 객체 집합 구조를 말한다
• 정점, 간선으로 이루어져 있고 모든 정점의 쌍 반드시 간선으로 연결 되는 것은 아니다
• 하나의 간선은 두 개의 정점을 연결한다

 

오일러 경로

쾨니헤스베르크 다리의 그래프 구조(오일러 경로)

• 그래프에 존재하는 모든 정점이 한 번씩만 방문하는 경로(한붓그리기,시작과 끝이 같아야한다)
• 모든 정점이 짝수 개의 차수를 갖지 않으면 오일러 경로가 아니다
• 오일러 경로를 가진 그래프를 오일러 그래프라고 한다

 

해밀턴 경로

해밀턴 순환을 가진 외판원 문제

• 각 정점을 한번 씩 방문하는 무향 또는 유향 그래프 경로를 말한다(시작과 끝이 같아야한다)
• 해밀턴 경로를 가진 그래프를 해밀턴 그래프라고 한다
• 오일러 경로와의 차이는 오일러는 간선기준, 해밀턴 경로는 정점을 기준으로 한다는 것이다

 

그래프 순회

BFS와 DFS 

• 그래프 탐색이라고도 불리며, 그래프의 각 정점을 방문하는 과정을 말한다
• 크게 깊이 우선 탐색(DFS) 와 너비 우선 탐색(BFS) 2개로 나뉜다

 

DFS(깊이 우선 탐색)

일반적으로 DFS는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. 코딩 테스트 시에도 재귀 구현이 더 선호되는 편이다.

 

재귀 구조로 표현

# 재귀를 이용한 DFS 구현 수도코드
DFS(G,v)
  label v as discovered
  for all directed edges from v to w that are in G.adjacentEdges(v) do
    if vertex w is not labeled as discovered then
      recursively call DFS(G,w)

 

 

이 수도코드는 정점 v의 모든 인접 유향 간선들을 반복하라고 표기되어있다. 다음 수도코드를 파이썬 으로 구현해보면 다음과 같다.

def recursive_dfs(v, discovered=[]):
  discovered.append(v)
  for w in graph[v]:
    if w not in discovered:
      discovered = recursive_dfs(w, discovered)
  return discovered
  
  
  # 결과
  f'recursive dfs:{recursive_dfs(1)}'
  'recursive dfs: [1, 2, 5, 6, 7, 3, 4]'

 

 

스택을 이용한 반복 구조로 구현

# 반복을 이용한 DFS 구현 수도코드
DFS-iterative(G, v)
  let S be a stack
  S.push(v)
  while S is not empty do
    v = S.pop()
    if v is not labeled as discovered then
      label v as discovered
      for all edges from v to w in G.adjacentEdges(v) do
       S.push(w)

이 수도코드는 스택을 이용해 모든 인접 간선을 추출하고 다시 도착점인 정점을 스택에 삽입하는 구조로 구현되어 있다.

파이썬 코드로 구현하면 다음과 같이 된다.

def iterative_dfs(start_v):
  discovered = []
  stack = [start_v]
  while stack:
    v = stack.pop()
  if v not in discovered:
    discovered.append(v)
    for w in graph[v]:
      stack.append(w)
return discovered

 

BFS(너비 우선 탐색)

DFS보다는 쓰임새가 적지만, 최단 경로를 찾는 다익스트라 알고리즘 등에 쓰인다.

 

 

큐를 이용한 반복 구조

# 큐를 이용한 BFS 수도코드
BFS(G, start_v)
  let Q be a queue
  label start_v as discovered
  Q.enqueue(start_v)
  while Q is not empty do
    v := Q.dequeue()
    if v is the goal then
      return v
    for all edges from v to w in G.adjacentEdges(v) do
      if w is not labeled as discovered then
       label w as discovered
       w.parent := v
       Q.enqueue(w)

리스트의 모든 인접 산선을 추출하고 도착점인 정점을 큐에 삽입하는 코드이다. 이것을 파이썬 코드로 구현하면 다음과 같다.

def iterative_bfs(start_v):
  discovered = [start_v]
  queue = [start_v]
  while queue:
    v = queue.pop(0)
    for w in graph[v]:
      if w not in discovered:
        discovered.append(w)
        queue.append(w)
  return discovered
  
 # 결과
 f'iterative bfs: {iterative_bfs(1)}'
 'iterative bfs: [1, 2, 3, 4, 5, 6, 7]'