[자료구조 및 알고리즘] Graph1 (C++)

Graph

그래프(Graph)란?

그래프는 아이템들과 이들 사이의 연결 관계를 표현하는 비선형 자료구조입니다. 그래프의 각 요소를 '정점(Vertex)'라고 하고, 이들 사이를 연결하는 것을 '간선(Edge)'이라고 합니다.

그래프는 리스트나 스택, 큐와 같은 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이합니다.

용어 정리

• 정점(Vertect): 키와 부가 정보를 담는 그래프의 기본 단위
• 간선(Edge): 두 정점을 잇는 연결(방향성을 가질 수 있음)
• 가중치(Weight): 간선을 따라 이동할 때의 비용
• 경로(Path): 간선으로 이어진 정점들의 순서
• 사이클(Cycle): 시작·종료 정점이 같은 경로

그래프 유형

• 무향 그래프(Undirected Graph)
  • 방향 표시가 없는 그래프
  • 어느 방향으로도 이동 가능하다는 뜻
• 유향 그래프(Directed Graph)
  • 표시된 방향으로만 이동이 가능하다는 뜻
• 가중치 그래프(Weighted Graph)
  • 간선 사이를 이동하는 비용을 나타낸 그래프
• 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)
  • 말 그래도 사이클이 없는 방향 그래프임
• 사이클이 없는 무향 그래프 == 트리

수학적 표현

• 그래프는 $G = (V, E)$ 형태로 정의
  • $V$ : 정점 집합 {v₀, v₁, …}
  • $E$ : 간선 집합 {(from, to, weight)}

그래프 표현 방법 두 가지

방식	특징	장단점
인접 행렬 (Adjacency Matrix)	n×n 2차원 배열에 가중치 저장	연결 여부를 한눈에 파악 가능 희소 그래프엔 메모리 낭비
인접 리스트 (Adjacency List)	각 정점이 (이웃, 가중치) 목록 보유	메모리 효율적·특정 정점의 이웃 탐색 용이

---

그래프 순회(탐색)

그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색(완전탐색)하는 것을 의미합니다. 그래프 순회 방법에는 두 가지 방법이 존재하는데, 바로 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS)입니다.

DFS(Depth First Search)

깊이 우선 탐색은 시작 정점의 한 방향으로부터 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 이동할 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법입니다.

가장 마지막에 만났던 갈림길의 정점으로 되돌아가야 하므로 후입선출 구조인 스택을 사용하는 것이 구현에 용이합니다. 또는 재귀 호출이 콜 스택에 저장해놓는 방식으로 동작하므로, 재귀 호출을 활용하는 것도 구현에 용이합니다.

작동 원리

1. 시작 노드를 스택에 넣고 방문 처리
2. 스택이 빌 때까지:

• 스택의 top의 정점을 꺼내 인접 정점을 살펴봄
• 아직 방문하지 않은 정점을 스택에 넣고 방문 처리

3. 종료

BFS(Breadth First Search)

개념

• 그래프를 레벨-순으로 탐색하는 알고리즘

• 큐(Queue)를 사용해 같은 레벨의 정점들을 먼저 방문하고, 그다음 레벨로 넘어감

• 무가중치 그래프에서 최단 경로(edge = 1 cost) 를 찾을 때 자주 쓰임

• 시간 복잡도 O(V + E) (정점 + 간선), 공간 복잡도는 방문 여부 저장 + 큐 크기

작동 원리

1. 시작 정점을 큐에 넣고 방문 처리
2. 큐가 빌 때까지:
   • 맨 앞 정점을 꺼내 인접 정점을 살펴봄
   • 아직 방문하지 않은 정점을 큐에 넣고 방문 처리
3. 종료

출처

https://velog.io/@tomato2532/%EA%B7%B8%EB%9E%98%ED%94%84
https://wikidocs.net/133051