Graph

Graph

 

그래프 (Graph)

정점(Vertex, Node)과 간선(Edge)으로 이루어진 자료구조

여러 개체(정점)와 그 관계(간선)를 표현

현실 세계의 다양한 관계(도로망, SNS 친구 관계, 컴퓨터 네트워크 등)를 모델링할 때 사용함

 

그래프의 구성 요소

• 정점(Vertex) : 그래프의 기본 단위 (ex. 사람, 도시, 웹페이지)
• 간선(Edge) : 두 정점을 연결하는 선 (ex. 친구 관계, 도로, 링크)

방향이 없으면 무향 그래프 (Undirected Graph)

방향이 있으면 유향 그래프 (Directed Graph)

• 가중치(Weight) : 간선에 붙는 값 (ex. 거리, 비용, 시간)

 

그래프의 종류

 

1. 무방향 그래프 (Undirected Graph)

A-B는 B-A와 동일

친구 관계, 연결망 표현

 

2. 방향 그래프 (Directed Graph, Digraph)

A→B와 B→A가 다름

팔로우 관계, 웹 링크

 

3. 가중치 그래프 (Weighted Graph)

간선에 비용(가중치)이 붙음

최단 경로 문제

 

4. 비가중치 그래프 (Unweighted Graph)

단순히 연결만 있음

 

5. 사이클 그래프 / 비사이클 그래프

사이클(Cycle) : 한 정점에서 시작해 다시 돌아오는 경로가 있는 경우

 

그래프의 표현 방법

 

인접 행렬 (Adjacency Matrix)

• 2차원 배열로 표현
• 정점 i, j가 연결되면 matrix[ i ][ j ] = 1 (또는 가중치 값)
• 장점 : 구현이 간단하다, 두 정점 연결 여부 확인 O(1)
• 단점 : 메모리 낭비 (간선이 적은 희소 그래프에서 비효율적)

인접 리스트 (Adjacency List)

• 각 정점마다 연결된 정점을 리스트로 표현
• 장점 : 메모리 효율적, 특히 희소 그래프에서 유리하다.
• 단점 : 특정 간선 존재 여부 확인은 느리다 (O(V))

 

그래프 탐색 알고리즘

1. DFS (깊이 우선 탐색, Depth First Search)

• 한 경로를 끝까지 탐색 후 다른 경로를 탐색한다.
• 재귀나 스택 사용

   2. BFS (너비 우선 탐색, Breadth First Search)

• 시작점에서 가까운 정점(같은 거리 레벨)부터 탐색
• 큐 사용 → 최단 경로 탐색에 활용

 

동작 원리

 

DFS

• 자료 구조 : 스택
• 절차

1. 정점 방문 → 2. 인접 정점으로 들어감 → 3. 더 갈 곳이 없으면 백트래킹(되돌아오기)

• 간선 분류(유향 그래프) : 트리 / 뒤(Back) / 앞(Forward) / 교차(Cross) 간선을 통해 사이클 유무 등 분석 가능

BFS

• 자료 구조 : 큐
• 절차

1. 시작 정점을 큐에 넣고 방문 표시 → 2. 큐에서 하나 꺼내 인접 정점을 차례대로 넣기 → 3. 큐가 빌 때까지 반복

• 결과 : 시작점으로부터의 최단 간선 수를 자연스럽게 계산

 

 

 

 

참고

 

https://hongcoding.tistory.com/78

[자료구조] 그래프(Graph) 개념 정리