[자료구조] 그래프 (Graph)

■ 의의

현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현

트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯.

 

■ 구성

(1) 정점 (Vertex) : 데이터를 표현 (사물, 개념 등)
(2) 간선 (Edge) : 정점들을 연결하는데 사용

 

 

 

[사용 예시]

1. 소셜 네트워크 관계도

2. 지하철 노선도

3. 최적 길 판단

4. 다수 간의 호감도 등

 

■ 종류

(1) 가중치 그래프 (Weighted Graph) 

정점과 정점 사이를 잇는 간선에 가중치(비용)가 주어진 그래프를 뜻한다.

(2) 방향 그래프 (Directed Graph)

정점과 정점 사이를 잇는 간선에 방향이 주어진 그래프를 뜻한다.

 

■ 표현 방법

(1) 인접 리스트 : 서로 연결되어 있는 애들만 데이터를 넣어주고 이중 벡터로 관리한다. 이를 이용해 연결되어 있는지 확인할려면 해당 버텍스를 담고있는 벡터 컨테이너에 접근 후 순회해야한다.

위 방향 그래프 기준

(2) 인접 행렬 : 연결 여부를 나타내는 정점 목록을 행렬(matrix) 형태로 관리한다. 메모리 소모는 심하지만, 빠른 접근이 가능하다

 

 

■ 순회 (traversal) 방법

모든 정점을 방문하는 작업이다. 그래프의 정점들은 트리와 달리 양방향일 수 있다. 그렇기에 탐색 중 자기 자신으로 돌아올 가능성이 있기에 동일한 정점이 다시 처리되지 않도록 정점을 방문(vistied) 후 혹은 발견 (discovered) 후 표시를 해줘 중복 방문을 회피한다.

 

대표적으로 DFS, BFS 두 가지 방법이 있다.