그래프

요약 데이터의 원소에 해당하는 정점(Vertex)과 정점간의 관계를 간선(Edge)으로 연결하여 표현한 형태의 자료구조.

그래프는 꼭짓점과 변의 집합을 이루는 순서쌍을 의미하며, 관계를 간선과 정점으로 표현한 구조이다. 간선으로 연결한 두 정점을 '인접(Adjacent)해 있다' 혹은 '이웃 관계'라고 표현하며, 그래프에서 정점들이 연결된 다양한 노선을 경로라고 표현한다.

그래프의 유형

· 무방향성 그래프(Undirected Graph) : 방향성이 없는 그래프로, (A, B) = (B, A)이다.
· 방향성 그래프(Directed Graph) : 방향성을 가지고 표현한 그래프로, (A, B) ≠ (B, A)이다.
· 가중치 그래프(Weighted Graph) : 간선에 가중치를 할당한 그래프이다.

그래프의 탐색

그래프는 연결된 정점을 탐색하는데 크게 두 가지 탐색 방법이 있다.
· DFS(Depth First Search) : 시작 정점부터 더 이상 길이 안 보일 때까지 탐색하는 깊이 우선 탐색 방법이다.
· BFS(Breadth First Search) : 시작 정점부터 옆으로 좌우로 탐색하는 너비 우선 탐색 방법이다.