01. Graph

---

🔨 1. Graph의 정의 및 구조

정의

• 그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

구조

1. 직접적인 관계가 있는 경우 -> 두 점 사이를 이어주는 선이 있다.
2. 간접적인 관계인 경우 -> 몇 개의 점과 선에 걸쳐 이어진다.
3. A, B, C.. 과 같이 하나의 점을 -> 정점(vertex)라고 하고
4. 하나의 선을 -> 간선(edge)라고 한다.

🔨 2. Graph의 표현방식

📈 인접행렬(Adjacency Matrix, 어드제이선씨 매트릭스)

• 두 정점을 이어주는 간선이 있다면 두 정점은 인접하다.
• 입접 행렬의 인접 상태는 → 2차원의 배열 형태로 나타내고,
  1. 인접해있다면 → 1 (true)
  2. 인접해있지 않다면 → 0 (false)
• 만약 가중치 그래프라면 → 1 대신 의미있는 값을 저장한다.
  • ex) 네비게이션이라면, 정점간의 거리 등

💡 인접 행렬로 표현하기

A의 진출차수는 1개 : A —> C
[0][2] === 1
B의 진출차수는 2개 : B —> A, B —> C
[1][0] === 1
[1][2] === 1
C의 진출차수는 1개: C —> A
[2][0] === 1

🔎 인접 행렬은 언제 사용할까?

• 인접행렬은 한개의 큰 표와 같은 모습을 하고 있어 → 두 정점 사이에 관계 유무를 확인할 때 용이하다.
• 또 가장 빠른 경로를 찾고자 할 때 주로 사용된다.

📉인접 리스트(Adjacency LIst)

• 강 정점이 어떤 정점과 인접하는지 → 리스트 형태로 표현한다.
• 각 정점마다 하나의 리스트를 가지고 있고 → 이 리스트는 자신과 인점한 다른 정점을 담고 있다.

🔎 인접 리스트는 언제 사용할까?

• 메모리를 효율적으로 사용하고 싶을 때 사용한다.
• 인접 행렬은 연결 가능한 모든 경우의 수를 저장하므로 → 상대적으로 메모리를 많이 차지한다.

🔨 3. 알아둬야 할 Graph 용어들

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
• 간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
• 비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
• 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.

✏️ 추가 !

• 정점은 Node, 간선은 edge라고 통용적으로 많이 부른다.

🔨 4. Graph의 실사용 예제

→ 네비게이션

1️⃣ 비가중치 그래프

• 가중치(연결 강도)가 적혀있지 않은 그래프를 말한다.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}

console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

2️⃣ 가중치 그래프

• 간선에 연결 강도(가중치)를 표현한 그래프를 말하며, 네비게이션의 경우 → 각 정점(도시)간의 거리가 가중치가 될 수 있다.

정점: 서울, 대전, 부산
간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울

🔨 4. Graph의 추가 공부

• 그래프 안에 서클이 존재하면 →Cyclic Graph라고 부르며
• 반대는 Acyclic Graph라고 한다.
  

02. BFS와 DFS

---

✏️ 그래프 탐색의 목적

하나의 정점에서 시작해 → 그래프의 모든 정점을 한 번씩 방문(탐색)하는 것이다.
그래프튼 비선형 자료 구조이기 때문에 → 데이터가 배열처럼 정렬되어 있지 않아, 원하는 자료를 찾으려면 하나씩 모두 방문해야 한다.

🔨 1. ↔️ 너비 우선 탐색, BFS(Breadth-First Search)

• 너비를 우선적으로 탐색하는 방법으로, 두 정점 사이의 최단 경로 를 찾을 때 사용한다.
• ex. 한국 → 미국으로 가는 최단 경로 (직항, 경유 1회, 경유 2회 …)

🔨 2. ↕️ 깊이 우선 탐색, DFS(Depth-First Searth)

1. 한 정점에서 시작해 → 하나의 경로의 끝까지 완벽하게 탐색한 후
2. 찾는 값이 아리다면 다음 경로로 넘어가 탐색한다.

• BFS보다 탐색 시간은 좀 걸리지만 모든 노드를 완전히 탐색한다는 장점이 있다.

종합퀴즈 속 BFS와 DFS

---

A. 너비 우선 탐색(BFS)는 하나의 정점을 기준으로 목표하는 정점까지 가능 방법을 탐색할 때 → 하나의 정점에서 가장 가까운 정점부터 탐색한다.

B. 너비 우선 탐색(BFS)은 출발하는 정점과 가장 가까운 정점부터 탐색하기 때문에 → 경로 탐색 시 가장 먼저 찾아지는 해답이 곧 최단거리이다.

C. 깊이 우선 탐색(DFS)은 하나의 경로를 끝까지 탐색한 후, 목표한 정점이 도착지점이 아니라면 → 다음 경로로 넘어가는 탐색 방법이다.

D. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 모두 정점을 한번씩 방문하고, 방문한 정점은 다시 방문하지 않는다.