# 그래프, DFS, BFS

### 그래프

<figure><img src="/files/rlDSsBqJugKKCUGp94PI" alt=""><figcaption></figcaption></figure>

이미지 출처 : <https://elisha0103.tistory.com/24>

프로그래밍에서 그래프는 인접행렬, 인접리스트 방식으로 표현된다.

인접행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

* 메모리를 더 많이 쓰는 대신, 두 정점이 연결되었는지 확인하는 속도가 빠르다.

인접리스트: 리스트로 그래프의 연결 관계를 표현하는 방식

* 메모리를 덜 쓰는 대신에 두 정점의 연결 여부를 확인하는 데 시간이 걸린다.

간선의 개수가 많다면 인접 행렬이 유리하고, 간선의 개수가 적다면 인접 리스트가 유리하다.

### 그래프의 종류

1. **무방향 그래프(Undirected Graph)**:
   * 정점 간의 연결이 방향성을 가지지 않는 그래프입
2. **방향 그래프(Directed Graph)**:
   * 정점 간의 연결이 방향성을 가지는 그래프
3. **가중치 그래프(Weighted Graph)**:
   * 각 간선에 가중치(Weight)가 부여된 그래프

### 그래프의 표현 방식

**1. 인접 행렬(Adjacency Matrix)**:

* 행렬의 각 요소 (i, j)는 정점 i에서 정점 j로의 간선이 있는지 여부를 나타낸다.\
  간선이 있으면 1(또는 가중치 값), 없으면 0으로 표시한다.
* 장점: 두 정점 간의 간선 존재 여부를 O(1) 시간에 확인할 수 있다.
* 단점: 메모리 사용량이 많으며, 간선 수가 적은 희소 그래프(Sparse Graph)에서는 비효율적이다.

```
     A B C
   A 0 1 0
   B 1 0 1
   C 0 1 0
```

**2. 인접 리스트(Adjacency List)**:

* 각 정점에 대해 해당 정점과 연결된 모든 정점을 리스트로 저장한다.
* 장점: 메모리 사용량이 적으며, 간선이 적은 그래프에서 효율적이다.
* 단점: 두 정점 간의 간선 존재 여부를 확인하는 데 O(n)의 시간이 걸릴 수 있다.

```
   A: B
   B: A, C
   C: B
```

### 깊이 우선 탐색(DFS)

아래 레벨에 방문 안 한 노드가 있으면 그 노드를 우선 탐색\
한 놈만 팬다

* 특정 경로가 존재하는지, 또는 모든 경로를 찾는 문제에 유용
* 그래프에서 사이클이 있는지 검사할 수 있다
* 재귀나 스택으로 구현한다
* 결과 하나를 만들어낸 뒤 다음 결과를 만들러 가기 때문에 검증하기가 쉽다

### 넓이 우선 탐색(BFS)

레벨별로 탐색한다\
여러 놈을 한 대씩 때리며 간다

* 무방향 그래프에서 시작 정점에서 다른 정점까지의 최단 경로 찾을 수 있음
* 큐나 링크드 리스트를 사용한다
* DFS에 비해 경로 운빨을 덜 탄다 (시간 복잡도가 낮다)

**BFS (Breadth-First Search) 구현**

```python
from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 기록할 집합
    queue = deque([start])  # 시작 노드를 큐에 삽입
    visited.add(start)

    while queue:
        vertex = queue.popleft()  # 큐에서 노드를 하나 꺼냄
        print(vertex, end=" ")  # 방문한 노드를 출력

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)  # 인접한 노드를 큐에 삽입
                visited.add(neighbor)  # 방문한 노드로 표시

# 그래프 예제 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# BFS 실행
print("BFS:")
bfs(graph, 'A')
```

**DFS (Depth-First Search) 구현 - 재귀 방식**

```python
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")  # 방문한 노드를 출력

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# DFS 실행 (재귀 방식)
print("\nDFS (Recursive):")
dfs_recursive(graph, 'A')
```

**DFS (Depth-First Search) 구현 - 스택 사용**

```python
def dfs_stack(graph, start):
    visited = set()  # 방문한 노드를 기록할 집합
    stack = [start]  # 시작 노드를 스택에 삽입

    while stack:
        vertex = stack.pop()  # 스택에서 노드를 하나 꺼냄
        if vertex not in visited:
            print(vertex, end=" ")  # 방문한 노드를 출력
            visited.add(vertex)

            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)  # 인접한 노드를 스택에 삽입

# DFS 실행 (스택 사용)
print("\nDFS (Stack):")
dfs_stack(graph, 'A')
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/dfs-bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.