210624 그래프(Graph)

그래프(Graph) : 연결되어 있는 개체간의 관계를 표현하는 자료 구조

트리도 그래프의 일종이라고 볼 수 있다.

 

그래프의 용어

그래프는 ( V , E ) 으로 표시됨

V는 정점(vertices)들의 집합

E는 간선(edge)들의 집합

정점과 간선은 모두 관련되는 데이터를 가질 수 있음 ( ex - 정점은 도시의 이름 간선은 도로의 길이 등 )

인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점

정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 

진입 차수(in - degree) : 방향 그래프에서 외부에서 오는 간선의 수

진출 차수(out - degree) : 방향 그래프에서 외부로 향하는 간선의 수 

단순 경로(simple path) : 경로 중에서 반복되는 정점 없는 경우

사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

경로의 길이(path length) : 경로를 구성하는데 사용된 간선의 수

 

그래프의 종류

• 무방향 그래프(undirected graph) : 간선을 통하여 양방향 이동가능, (A , B) == (B , A)
• 방향 그래프(directed graph) : 간선에 방향성 존재, <A, B> != <B, A>
• 가중치 그래프(weighted graph) : 간선에 비용이나 가중치가 할당된 그래프

 

그래프 표현 예시

 

그래프 표현 방법

• 인접 행렬(adjacent matrix) : 2차원 배열 사용 표현
  • 장점 : 두 정점을 연결하는 간선의 존재 여부를 O(1) 안에 알 수 있음
  • + 정점의 차수는 O(N) 안에 알 수 있음 (인접 배열의 i 번째 행 또는 열 모두 더함)
  • 단점 : 어떤 노드에 인접한 노드들 찾기 위해 모든 노드 순회해야 함
  • + 그래프에 존재하는 모든 간선의 수는 O(N^2)안에 알 수 있음 (인접 행렬 전체 조사)
• 인접 리스트(adjacency list) : 연결리스트를 사용 표현
  • 장점 : 어떤 노드 기준으로 인접한 노드들 쉽게 찾을 수 있음
  • + 그래프에 존재하는 모든 간선의 수  O(N+E)안에 알 수 있음 (인접 리스트 전체 조사)
  • 단점 : 정점의 차수만큼의 시간이 필요

                                  인접행렬                                                 인접리스트

 

그래프의 탐색 

• 깊이 우선탐색(DFS)
• 너비 우선탐색(BFS)

둘 다 중요한 내용이라 알고리즘 내용으로 본격적으로 들어가서 좀 더 파고들어서 정리하겠다