그래프(Graph)

그래프

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조를 의미한다. 연결된 정점간의 관계를 표현할 수 있는 자료구조로 지하철 노선도나 통신 네트워크, 길 추천 등에 사용된다. 

 

그래프의 구조

• 정점(Vertex) : 각 노드를 의미한다. 
• 간선(Edge) : 노드와 노드를 연결하는 선(Link, Branch)
• 인접 정점(Adjacent Vertex) : 간선 하나를 두고 바로 연결 된 정점을 의미함.
• 정점의 차수 (Degree) 
  • 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 * 2

무방향 그래프

• 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수(Out-Degree) : 방향 그래프에서 외부로 나가는 간선의 수
• 경로 길이(Path-length) : 경로를 구성하는데 사용된 간선의 수
• 단순 경로(Simple path) :  경로 중에서 반복되는 정점이 없는 경우
• 사이클(Cycle) : 단순 경로의 시작 정점과 끝정점이 동일한 경우

방향 그래프

그래프의 특징과 트리와의 차이

	그래프	트리
개요	노드와 간선으로 이루어진 구조	그래프의 한 종류
방향성	방향 그래프, 무방향 그래프	방향 그래프
사이클	Cyclic	Acyclic
모델	네트워크 모델	계층 모델
루트 노드	루트 노드 X	최상위 노드
부모-자식	부모-자식 관계 X	인접한 상하위 노드
간선 수	그래프에 따라 간선의 개수 다름	N개의 노드로 구성된 트리의 간선의 수 n-1개
순회	DFS, BFS	Pre, In, Post - Order / Level Order
경로	2개 이상	노드간의 경로는 1개

 

그래프의 종류(1)

- 무방향 그래프

• 간선에 방향이 없는 그래프(양방향 이동 가능)
• 정점 A-B 간선의 표현 (A,B) = (B,A)

- 방향 그래프

• 간선에 방향이 있는 그래프(해당 방향으로만 이동 가능)
• 정점 A -> B 간선의 표현 <A,B> ≠ <B,A>

 

그래프의 종류 (2)

- 가중치 그래프

• 간선에 값이 있는 그래프(이동 비용)

- 완전 그래프

• 모든 정점이 서로 연결되어 있는 그래프
• 정점이 N개 일 경우, 간선의 수는 n(n-1) / 2 개

 

그래프 탐색(DFS)

- 깊이 우선 탐색(Depth First Search)

• 각 노드에 방문했는지 여부를 체크할 배열과 스택을 이용하여 구현

 

그래프 탐색(BFS)

- 너비우선 탐색(Breath First Search)

• 각 너비에 방문했는지 여부를 체크 할 배열과 큐 자료구조를 이용하여 구현

 

그래프 구현(1)

- 인접 행렬(Adjacent Matrix)

• 2차원 배열을 활용함.

- 인접행렬의 장단점

• 간선 정보의 확인과 업데이트가 빠름 O(1)
• 인접 행렬을 위한 메모리 공간 차지

 

그래프의 구현(2)

- 인접 리스트(Adjacency List)

• 연결리스트 이용하여 구현

- 인접 리스트의 장단점

• 메모리 사용량이 상대적으로 적고, 노드의 추가 삭제가 빠름
• 간선 정보 확인이 상대적으로 오래 걸림. 

인접 행렬 vs 인접 리스트

- 인접 행렬

• 노드의 수가 적고 간선이 많을 때 유리함. 

- 인접리스트

• 노드의 개수가 많고 간선의 수가 적을 때 유리함. 

	인접행렬	인접리스트
특정 간선 검색	O(1)	O(degree(V))
정점의 치수 계산	O(N)	O(degree(V))
전체 노드 탐색	O(N^2)	O(E)
메모리	N x N	N + E

N : 전체 정점의 개수, E : 전체 간선의 개수