C++

[C++] 그래프, DFS, BFS 탐색

k-codestudy 2025. 3. 17. 08:34

1. 그래프

설명 

그래프는 객체 사이의 연결 관계를 표현하는 자료구조이다.

리스트, 스택, 큐 같은 선형 자료구조는 요소 간의 선형적인 순서(선,후 관계) 만을 나타낼수 있기 때문에 1:N 또는 N:M 관계를 표현하기 어렵다.

트리는 하나의 노드가 여러 개의 노드와 연결될 수 있지만, 부모- 자식 간의 계층적 관계만을 표한할 수 있어 일반적인 관계를 나타내기에는 한계가 있다.

그래프는 이러한 한계를 극복하고, 객체 간의 다양한 연결관계를 표현할 수 있는 자료구조이다.

 

개념

 

그래프는 노드(Node 또는 정점 Vertex)와 간선(Edge)의 집합이다.

  • 노드(Node 또는 정점 Vertex) : 그래프에서 데이터(객체)를 나타내는 요소
  • 간선(Edge) : 노드 간의 연결 관게를 나타내는 요소

예를 들어 여로 도시가 있고 이들 사이를 잇는 고속도로가 있다면, 각 도시는 그래프의 노드(정점)가 되고, 도시들을 연결하는 고속도로는 간선(Edge)이다.

 

표현 방식 

 

인접 행렬 

인접 행렬은 2차원 배열(행렬)로 간선 정보를 저장하는 방식이다.

  • 그래프의 두 정점이 연결되어 있으면 1을 저장하고, 연결되어 있지 않으면 0을 저장한다.
  • 가중치 그래프의 경우, 1 대신 해당 간선의 가중치(weight)를 저장한다.

행렬의 행과 열:

  • 각 행(row)은 간선의 출발 노드
  • 각 열(column)은 간선의 도착 노드

 

방향 그래프 

[ 사진 첨부 ]

 

무방향 그래프

[ 사진 첨부 ]

무방향 그래프는 양방향 그래프와 같다.

점선으로 표시된 대각선을 기준으로 대칭을 이룸

 

인접 리스트

인접 리스트는 각 노드가 연결된 노드들의 리스트를 저장하는 방식이다.

  • 각 행(row)이 특정 정점을 의미하고, 해당 행에 연결된 다른 정점들을 리스트로 저장한다.
  • 리스트 내의 노드들은 인접한 정점들의 집합을 나타낸다.
  • 정점의 개수만큼 헤드 포인터 배열을 사용하여 인접 리스트를 관리한다.

방향 그래프 

[ 사진 첨부 ]

 

무방향 그래프

[ 사진 첨부 ]

무방향은 역시 양방향으로 생각해서 적용한다.

 

장단점 

인접 행렬 

장점 : 특정 노드로 가는 간선이 있는지 여부를 O(1)만에 알아 낼 수 있다. 예를 들어 0에서 3으로 가는 간선이 있는지 알기 위해선 배열[0][3]의 값을 보면 알수 있기 때문

단점 : 간선의 개수와 상관없이 항상 N제곱의 메모리를 사용한다.

 

인접 리스트

장점 : 간선의 개수가 적을 수록 메모리를 덜 차지한다.

단점 : 특정 노드로 가는 간선이 있는지 알기 위해선 순차 탐색을 하며 살펴봐야 한다.O(N), 예를 들어 0에서 3으로 가는 간선이 있는지 알기 위해선 0행에 있는 데이터를 순차 탐색하며 '3'이 있는지를 살펴봐야 한다.

 

 

2. DFS

정의 

DFS(Depth First Search)는 한 방향으로 갈 수 있을 때까지 탐색하다가, 더 이상 갈 곳이 없으면 되돌아가서 다른 경로를 탐색하는 방식이다.

  • 스택(Stack) 혹은 재귀 함수(Recursion) 를 사용하여 구현된다.
  • 탐색 순서가 한 갈래로 계속 진행되므로, 최단 경로를 보장하지 않는다.

[사진 첨부 ]

구현 

 

3.BFS

정의 

BFS(Breadth First Search)는 가까운 정점부터 탐색하고, 멀리 있는 정점을 나중에 탐색하는 방식이다.

  • 큐(Queue) 를 사용하여 구현된다.
  • DFS와 다르게, 최단 경로를 보장할 수 있다.

[사진 첨부 ]

구현