Graph

• 여러 개의 정점(vertex)와 그들을 이어 주는 간선(edge) 사이의 관계를 표현
• 무향(undirected): vertex 간의 edge에 방향이 명시되어 있지 않아, 양방향으로 이동 가능
• 단방향(directed): vertex 간의 edge에 명시된 방향으로만 이동 가능 (양방향을 표현하려면 edge가 2개 필요)
• 진입차수(in-degree) / 진출차수(out-degree): 하나의 vertex에 진입하고 진출하는 edge의 수
• 인접(adjacency): 두 vertex가 하나의 edge로 직접적으로 연결되어 있을 경우 adjacent한 것으로 표현
• 자기 루프(self loop): 자신에게서 진출해서 곧바로 자기 자신으로 진입하는 edge
• 사이클(cycle): 특정 vertex에서 진출하여 (타 vertex들을 거쳐) 다시 시작 vertex로 돌아오는 길이 있다면 cycle이 존재

Adjacency list vs Adjacency matrix

두 개념 모두 하나의 graph 내에서 존재하는 edge들을 표현한 것이다.

Adjacency list

• 각 vertex가 어느 vertex와 연결되는지 리스트의 형식으로 표현
• edge가 존재하는 경우에만 저장하기에 메모리 효율이 높다.

let adjList = 
{"1": [2, 3],
"2": [3],
"3": [4],
"4": [1]}

Adjacency matrix

• 각 vertex가 어느 vertex와 연결되는지 표(매트릭스)의 형식으로 표현 (edge가 존재하면 1, 존재하지 않으면 0)
• 모든 경우의 수를 저장하기에 메모리 효율은 떨어지지만 특정 vertex간의 edge가 존재하는지 한눈에 파악하기에는 간편

let adjMatrix = 
[[0, 1, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[1, 0, 0, 0]]

BFS vs DFS

너비가 넓은 graph인지, 깊이가 깊은 graph인지 고려하여 더 짧은 쪽을 먼저 탐색하는 방법을 선택하는 것도 효율적이다.

Breadth-First Search (BFS)

• 가까운 정점부터 우선적으로 탐색한 후 조건에 맞지 않는 경우 다음 깊이로 넘어가 탐색
• 두 정점 사이의 최단 경로를 찾고 싶을 때 사용
• 흔히 queue를 이용해 구현

Depth-First Search (DFS)

• 하나의 경로를 끝까지 탐색한 후, 조건에 맞지 않는 경우 다음 경로로 넘어가 탐색
• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색하고 싶을 때 사용
• 보통 재귀로 구현