[Data Structure] Graph(그래프)

 

Graph(그래프)

정점(vertex)와 간선(edge)으로 구성된 자료 구조로 객체 간의 관계를 표현하는데 사용된다.

 

구성요소

정점 : 객체(데이터)를 저장하는 노드

간선 : 객체 간의 관계, 두 정점 간의 연결선

 

사용 예시 : 소셜 네트워크, 지도, 컴퓨터 네트워크

 

그래프의 종류

• 방향 그래프
  간선에 방향이 있어 A > B는 가능하지만 B > A는 별도로 정의해야 한다
  ex : 웹 페이지 링크, 종속성 관계
  
  종속성 관계란 의존성을 의미한다 하나의 노드가 다른 하나의 노드에 의존하거나 영향을 받는 관계를 나타낼 때 사용한다. 
  
  ex : 작업 A를 완료해야 B를 시작, 모듈 A가 모듈 B를 참조할 때(B가 없으면 A가 동작하지 않음), 어떤 과목을 학습할 때 다른 과목의 선행학습(기초 수학 > 미적분 > 공학 수학)
• 무방향 그래프
  간선에 방향이 없어 A - B는 양방향으로 연결된다
  ex : SNS의 맞팔로우
  
  
• 가중치 그래프
  간선에 가중치가 부여된 그래프
  가중치 : 비용, 거리, 시간 등
  ex : 택시요금, 자동차를 타고 이동 시 거리에 비례하여 걸리는 시간
• 비가중치 그래프
  간선에 가중치가 없는 그래프
  ex : 단순 연결 구조

 

트리와 그래프의 차이점

트리

• 계층적 구조를 가진 방향 그래프의 특수한 형태
• 항상 부모 > 자식으로 방향성이 정해져 있음
• 시작점인 루트 노드에 모든 노드가 연결됨
• 순환 구조 불가능
• ex : 계층 구조 표현(디렉토리 구조)

 

그래프

• 네트워크 구조로 표현되는 일반적인 데이터 구조
• 간선에 방향이 있을 수도 없을 수도 있음
• 반드시 계층이 요구되지 않음
• 순환 구조 가능
• ex : 사람들 간의 친구 관계(A와 B는 서로를 모르지만 C는 서로를 알고 있다, C는 D도 알고 있다

 

그래프의 표현 방식

Adjacency Matrix(인접 행렬)

• 그래프를 2차원 배열로 표현하는 방식
• 행과 열이 그래프의 정점(vertex)를 나타냄
• 특정한 두 정점 간에 간선(edge)이 존재하면 해당 위치에 값을 기록

값의 의미

• 0 or false : 두 정점 사이에 간선이 없음
• 1 또는 가중치 : 두 정점 사이에 간선이 있음 (가중치 그래프에서는 간선 값의 가중치를 저장)

 

ex:

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

 

장점

• 간선 존재 여부를 빠르게 확인 가능 O(1)
• 구현이 간단하고 메모리에서 정적으로 관리

 

단점

• 간선이 적은 희소 그래프에서 많은 공간을 낭비
• 모든 인접 노드 순회 시간은 O(V) : 모든 정점을 확인해야함

 

Adjacency List(인접리스트)

• 그래프를 연결리스트 또는 배열의 리스트 형태로 표현
• 각 정점에 대해 연결된 다른 정점들의 리스트를 저장

구조

• 리스트는 노드마다 동적으로 생성되고, 연결된 정점만 포함
• 메모리를 간선 개수에 비례하여 사용

ex

A : B, C

B : A, D

C : A

D : B

 

장점

• 효율적인 메모리 사용 : 간선이 적은 경우 공간 낭비가 적음
• 인접노드 순회 시간 : 연결된 노드만 확인 O(K) k : 간선수

 

단점

• 간선 존재 여부 확인이 느림 : 특정 간선이 있는지 확인하는데 O(K)
• 구현이 복잡

 

희소 그래프와 밀집 그래프

간선의 수에 따라 희소 그래프와 밀집 그래프로 나눈다

 

희소 그래프

• 간선의 수가 적음
• 일반적으로 E << V의 제곱 (간선 E의 수가 정점 V의 제곱보다 훨씬 적음) 
• 간선 밀도가 낮다
• 인접 리스트로 표현(효율적인 메모리 사용)

밀집 그래프

• 간선의 수가 상대적으로 많음
• 일반적으로 E ≈ V의 제곱(간선 E의 수가 정점 V의 제곱에 가까움)
• 간선 밀도가 높음
• 인접 행렬을 사용 간선 존재 여부를 빠르게 확인하고 간선 수가 많아 메모리 낭비가 적음

간선의 밀도

• 간선 밀도의 계산은 E/V의 제곱으로 계산
• 밀도가 0에 가까우면 희소, 1에 가까우면 밀집그래프

 

그래프의 탐색 알고리즘

DFS(Depth-First Search)

깊이 우선 탐색으로 그래프의 한 경로를 따라 갈 수 있을 만큼 깊이 탐색한 뒤 갈 곳이 없으면 되돌아와 다른 경로를 탐색하는 방식

 

구현 방법

• 재귀 : 재귀 호출을 사용하여 스택 동작을 구현
• 스택 : 명시적으로 스택을 사용

동작 과정

1. 시작 노드에서 출발
2. 연결된 노드를 따라 깊이 탐색
3. 탐색할 곳이 없으면 되돌아와 새로운 경로 탐색

• 시간 복잡도 : O(V+E)
• 메모리 사용 적음
• 경로 찾기(미로 탐색 등)
• 사이클 검사 : 그래프가 순환인지 확인

BFS(Breadth-First Search)

너비 우선 탐색으로 시작 노드에서 가까운 노드를 먼저 모두 방문한 뒤, 그 다음 레벨의 노드들을 차례대로 방문하는 방식

 

구현방법

큐(Queue) : 방문할 노드를 큐에 추가하고, 큐에서 노드를 꺼내며 탐색

 

동작 과정

1. 시작 노드에 큐를 넣음
2. 큐에서 노드를 꺼내고 방문하지 않은 이웃 노드들을 큐에 추가
3. 큐가 빌때까지 반복

• 시간 복잡도 : O(V+E)
• 메모리 사용 많음
• 최단 거리 탐색
• 특정 깊이 노드 탐색

DFS와 BFS의 차이

• DFS는 스택 또는 재귀를 사용 깊이 우선 탐색
• BFS는 큐를 이용 너비 우선 탐색
• DFS는 경로를 따라가며, BFS는 계층적으로 탐색

그래프가 연결 그래프인지 확인하는 방법

• DFS 또는 BFS를 수행하여 모든 정점을 방문했는지 확인한다

그래프에서 사이클을 탐지하는 방법

• DFS를 수행하여 방문 중인 노드가 이미 방문된 노드라면 사이클이 존재한다

 

그래프 구현

Adjacency Matrix(인접 행렬)

https://github.com/9mans/Graph-Practice/blob/master/src/AdjacencyMatrix.java

Adjacency List(인접 리스트)

https://github.com/9mans/Graph-Practice/blob/master/src/AdjacencyList.java

DFS

https://github.com/9mans/Graph-Practice/blob/master/src/DFS.java

BFS

https://github.com/9mans/Graph-Practice/blob/master/src/BFS.java