[자료구조] 그래프

ERror.ASER·2021년 3월 9일

그래프 자료구조

자료구조

목록 보기

9/11

그래프

정점과 간선으로 이루어진 비선형 자료구조(정점간의 관계를 표현하는 조직도)
트리도 그래프의 일종이다.
네트워크 모델, 지하철 노선도, 도심의 도로
dfs, bfs

용어

정점(vertice) : node, 주로 데이터를 저장
간선(edge) : 링크(arcs). 정점과의 관계를 나타냄.
사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
인접 정점(adjacent verte) : 간선에 의해 연결된 정점.
단순 경로(simple-path): 같은 간선을 지나가지 않는 경로
차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정접의 수
진출 차수(out-degree) : 방향 그래프에서 한 노드에서 외부로 향하는 간선의 수
진입 차수(in-degree): 방향 그래프에서 외부 노드에서 들어오는 간선의 수

종류

무방향 그래프

두 노드 사이에 연결하는 간선에 방향이 없는 그래프

방향 그래프

두 노드 사이에 연결하는 간선에 방향이 있는 그래프
<A,B>와 <B,A>는 다르다.

가중치 그래프

간선에 비용이나 가중치가 할당된 그래프

완전 그래프

모든 노드가 간선으로 연결되어 있는 그래프

구현

인접행렬(Adjacency Materix)

2차원 배열을 이용하여 구현
구현이 용이하다.
정보 탐색 : O(1)
정보를 넣는 시간 : O(n^2)
무조건 2차원 배열이 필요

인접리스트(Adjacency List)

그래프의 노드들을 리스트로 표현
정보 탐색 : O(n), n: 간선의 개수
공간 낭비가 적음
인접행렬에 비해 정보 탐색 시간이 걸림
구현이 어려움

탐색

깊이 우선 탐색(DFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
넓게(wide) < 깊게(deep) 탐색하는 것이다.
사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

너비 우선 탐색(BFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
깊게(deep) < 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색