그래프

그래프의 개념

 

- 아이템들과 이들 사이의 연결관계를 표현하는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조

- 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가진 원소들을 표현하기에 편리함

- 정점: 그래프의 구성요소로서 하나의 연결점

- 간선: 두 정점을 연결하는 선

- 차수: 정점에 연결된 간선의 수

 

그래프의 종류

무향 그래프	유향 그래프
가중치 그래프	사이클 없는 방향 그래프(Directed Acyclic Graph)

 

<참고>

완전 그래프: 정점들에 대해 가능한 모든 간선을 가진 그래프

부분 그래프: 원래 그래프에서  일부의 정점이나 간선을 제외한 그래프

 

 

그래프의 표현

 

1) 인접행렬: 2차원 배열 이용하여 간선 정보 저장
     희소 그래프인 경우, 즉 정점 수 대비 간선 수가 적을 경우 매우 비효율

2) 인접 리스트: 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장(배열 안에 리스트 존재)

3) 간선 리스트: 간선(시작, 끝 정점)의 정보를 객체로 표현해 리스트에 저장

     간선을 하나의 객체로 표현, 가중치까지 필드로 담을 수 있어 용이

 

그래프 순회

 

비선형 구조인 그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것을 의미

방법1) 깊이우선탐색 DFS

방법2) 너비우선탐색 BFS