이 포스팅의 알고리즘 강의는 이곳에서 보실 수 있습니다.

그래프(Graph)란?

• 그래프 G = {V,E} 여기서 V는 노드(node)의 집합, E는 정점을 연결하는 선(edge)의 집합을 뜻한다. 즉, 그래프란 여러 개의 노드들이 존재하고 노드들 사이가 선으로 연결되어있는 상태를 말한다.
• n = |V|, m=|E|
• 위의 사진은 노드 사이의 선이 방향(화살표가 없는) 형태이다. 이런 형태를 무방향 그래프라고 한다.
• 방향그래프(Directed Graph)는 역시 G = (V, E)의 뜻은 같으나 선(edge)가 시작점과 도착점을 가진다 ex) (u, v)는 u로 부터 v로의 방향을 가진다는 것을 뜻한다.

그래프의 표현

• 그래프를 구현할 때는 2가지 방법으로 구현할 수 있다.
• 실제 자바를 기준으로 구현을 생각하면 2차원 배열로 구현하는게 좀 더 효율적일 수 있을것같다 (알고리즘 문제 풀이 기준으로)
• 위의 사진들은 무방향그래프를 기준으로 표현한 것이고 방향그래프의 표현은 아래와 같다.

그래프의 가중치

• 선(edge)의 존재를 나타내는 값으로 1 대신 에지의 가중치를 저장한다.
• 선에 가중치를 적용하는 특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서 거리나 비용을 의미하는 경우이면 선이 없으면 무한대, 2차원 행렬의 대각선에는 0을 넣을 수 있다.

경로와 연결성

• 무방향 그래프 G=(V, E)에서 노드 u와 노드 v를 연결하는 경로(path)가 존재할 때 v와 u는 서로 연결되어 있다고 말한다. (노드 4에서 3까지 가는 길)
• 모든 노드 쌍들이 서로 연결된 그래프를 연결된(connected) 그래프라고 한다. 아래 그림에서 1~8까지의 그래프를 뜻한다.
• 연결요소(connected component)는 하나의 그래프에 따로 떨어진 그래프가 있는걸 말한다. (그래프도 집합이므로 여러개가 존재 가능하다.)

그래프의 순회(traversal)

• 순회(traversal)은 그래프의 모든 노드들을 방문하는 일을 뜻한다.
• 대표적인 두가지 방법으로 BFS(Breadth-First-Search), 너비우선순회와 DFS(Depth-First-Search), 깊이우선순회가 있다.

너비우선순회 (BFS)

• BFS 알고리즘은 다음의 순서대로 노드들을 방문한다.
  • L0 = {s}, s는 출발노드(출발점)을 뜻한다.
  • L1 = L0의 모든 이웃 노드들
  • L2 = L1의 이웃들 중 L0에 속하지 않는 노드들
  • Li = L(i-1)의 이웃들 중 L(i-2) 에 속하지 않는 노드들
• s에서 이웃노드들을 방문하는 순서는 상관없다.
• Tree에서 배운 Level order traversal이 BFS의 2진 트리 버전이다.
• BFS를 구현할 떄 큐를 사용할 수 있는데 방법은 아래와 같다.
• 이런식으로 큐에 모든 노드를 넣고 뺄때까지 반복된다. 이웃들이 큐에 들어가는 순서는 상관없다.

스도코드

최단경로

• 출발점 s에서 Li에 속한 노드까지의 최단 경로의 길이는 i(경로에 속한 선(edge)의 개수)이다.
• BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.
• 입력: 방향 혹은 무방향 그래프 G=(V, E), 그리고 출발 노드 s가 노드의 집합 V에 속해 있을 때,
• 출력: 모든 노드 V에 대해서,
  • d[v] = s로 부터 v까지의 최단 경로의 길이(선(edge)의 개수)
  • t[v] = s로 부터 v까지의 최단 경로 상에서 v의 직전 노드(predecessor)
• 최단경로를 구하는 알고리즘을 추가한 스도코드(G는 그래프, s는 출발점)

깊이우선순회(DFS)

• BFS가 출발점에 인접한 노드들을 전부 방문하고 그 다음 노드들을 방문하는 것이었다면 DFS는 일단 출발점에서 이어진 한 노드를 리프노드까지 따라가보고 더 이상 진행할 노드가 없으면 들어온 방향으로 다시 돌아가 갈 수 있는 노드를 탐색하는 순회이다.

스도코드

DAG(Directed Acyclic Graph)

• Acyclic이란 사이클이 존재하지 않는 것을 뜻한다.

위상정렬(topological ordering)

• 우선순위로 노드들을 정렬한다.
• 위상정렬은 답이 여러개가 존재할 수 있다.
• 스도코드

최소신장트리(Minimum Spanning Tree)

최소비용 신장 트리(MST)

• 입력: n개의 도시, 도시와 도시를 연결하는 도로비용
• 문제: 최소의 비용으로 모든 도시들이 서로 연결되게 한다.
• 노드=도시, Edge=비용, 무방향-가중치그래프
• MST에서는 사이클이 존재하면 안된다. 왜냐하면 사이클은 중복연결이 된다는 것을 의미하는데 가중치가 최소가 되야하므로 사이클은 불필요하다.(회전하게 되면 계속해서 가중치가 증가한다.)

Generic MST 알고리즘

• 2번의 안전한 길(edge)찾기
• 스도코드

Kruskal의 알고리즘

• 에지들을 가중치의 오름차순으로 정렬한다.
• 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클을 형성하면 선택되지 않는다.
• n-1개의 에지가 선택되면 종료한다.
• 구현에서 생각해야 할 부분으로 사이클을 어떻게 검사할 것인가를 고려해야한다.
  • 각각의 연결요소를 하나의 집합으로 표현하자.

스도코드

• FIND - UNION 문제(각 집합을 어떻게 찾고 합칠건가?)

Prim의 알고리즘

• 임의의 노드를 출발노드로 선택
• 출발 노드를 포함하는 트리를 점점 키워간다.
• 매 단계에서 이미 트리에 포함된 노드와 포함되지 않는 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택.
• 가중치가 최소인 에지는 어떻게 찾을 것인가?
  • 각 노드에 2가지의 값을 유지하자.

스도 코드

최단경로(Shorest Path)

• 가중치(방향) 그래프 G=(V,E), 즉 모든 에지에 가중치가 있다.
• 경로 p=(v0, v1, …, vk)의 길이는 경로상의 모든 에지의 가중치의 합이다.
• 노드 u에서 v까지의 최단경로의 길이를 감마(u,v)라고 표시하자.
• 최단 경로의 어떤 부분경로도 역시 최단 경로이다.
• 최단경로는 사이클을 포함하지 않는다.

최단경로문제의 유형

• Single-source:
  • 하나의 출발노드 s로부터 다른 모든 노드까지의 최단경로를 찾아라.
  • 예: Dijkstra의 알고리즘
• All-pairs:
  • 모든 노드 쌍에 대해서 최단 경로를 찾아라.

Single-source 최단경로문제

• relax연산은 1개의 edge에 대한 연산이다. 각 u와 v노드 안에 값은 출발점 s로부터의 최단거리의 값인데 여기서 u를 거쳐 v로 가는 값이 s에서 v로 가는 값 보다 적을 시 relax연산으로 값을 바꾼다.
• 대부분의 Single-source 최단경로 알고리즘의 기본 구조
  1. 초기화: d[s]=0, 노드 v != s에 대해서 d[v]=무한대, t[v]=null.
  2. 에지들에 대한 반복적인 relaxation
• 스도코드

Dijkstra의 알고리즘