그래프

트리의 상위 개념 => 그래프

 

그래프란? 

 정점과 간선으로 이루어진 자료구조 -> 연결된 정점간의 관계를 표현할 수 있는 자료구조

 -But 트리와 다른점은 Cyclic하다. 

 

그래프의 구조

방향이 없음으로 무방향 그래프다.

1. 정점 : 각 노드

2. 간선: 노드와 노드를 연결하는 선

3. 인접 정점 : 간선 하나를 두고 바로 연결된 정점 (A의 인접 정점은 B,C)

4. 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수, 무방향 그래프의 모든 정점 차수의 합=간선 수 * 2

5. 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수

6. 진출 차수 : 방향 그래프에서 외부로 나가는 간선의 수

7. 경로 길이: 경로를 구성하는데 사용되는 간선의 수

8. 단순 경로: 경로 중에서 반복되는 정점이 없는 경우

9. 사이클 : 단순 경로의 시작과 끝점이 동일할 경우 

 

 

그래프 vs 트리

 

 

그래프의 종류

 가중치 그래프

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

 

 완전 그래프

 -모든 정점이 서로 연결되어 있는 그래프

 -정점이 N개일 경우, 간선의 수는 N(N-1)/2 개

 

그래프의 탐색

 

DFS 깊이 우선 탐색

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

BFS 너비 우선 탐색

-각 노드에 방문했는지 여부를 체크할 배열과 큐를 이용하여 구현 

 

그래프의 구현

 

인접행렬로 구현

-2차원 배열을 이용함

 

인접행렬의 장점

-간선 정보의 확인과 업데이트가 빠름 O(1)

-하지만 따로 배열을 사용함으로 메모리 공간을 차지

-노드의 갯수가 적고 간선의 수가 많을때 유리

 

연결리스트로 구현

-연결 리스트 사용

 

연결리스트의 장점

-메모리 사용량이 상대적으로 적다.

-노드의 삭제와 추가가 빠르다.

-노드의 개수가 많고 간선의 수가 적을때 유리

-하지만 간선 정보의 확인이 상대적으로 오래걸린다. 

 

 

 

N: 전체 정점 개수

E: 전체 간선 개수

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