[자료구조] 비선형 자료구조 - 그래프

이진이·2023년 8월 10일
data structure
0
post-thumbnail

✅ 비선형 자료구조 : i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조


그래프(Graph)?

정점(vertex)과 간선(edge)으로 이루어진 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현한다.

정점마다 간선이 있을 수도 있고 없을 수도 있다.


  • 정점(vertex) : 위치라는 개념. node라고도 부름

  • 간선(edge) : 위치 간의 관계. 즉, 노드를 연결하는 선. link, branch라고도 부름

  • 인접 정점 : 간선에 의해 직접 연결된 정점

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

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

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

  • 경로 길이 : 경로를 구성하는 데 사용된 간선의 수

  • 단순 경로 : 반복되는 정점이 없는 경로 (한붓그리기)

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



그래프 구현 방법

1. 인접 행렬 방식

그래프의 노드를 2차원 배열로 만든 것. 노드 간에 직접 연결이 되어있으면 1, 아니면 0을 넣어서 행렬을 완성시킨다.

2. 인접 리스트 방식

그래프의 노드를 리스트로 표현한 것. 정점의 리스트 배열을 만들어 관계를 설정하며, 노드들 간에 직접 연결이 되어 있으면 해당 노드의 인덱스에 그 노드를 삽입해 주면 된다.

장단점

 인접 행렬인접 리스트
장점- 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1)의 시간복잡도가 가능하다.
- 인접리스트에 비해 구현이 쉽다.		- 정점들의 연결 정보를 탐색할 때 O(n)의 시간복잡도가 가능하다.
- 필요한 만큼의 공간만 사용하기 때문에 공간 낭비가 적다.
단점- 모든 정점의 간선 정보를 대입해야 하므로 O(n^2)의 시간 복잡도가 소요된다.
- 무조건 2차원 배열을 사용해서 필요 이상의 공간이 낭비된다.		- 특정 두 점이 연결되어 있는지 확인하려면 인접행렬에 비해 시간이 오래걸린다.
O(E) (E는 간선의 개수)
- 구현이 비교적 어렵다.



그래프 종류

1. 무방향 그래프 : 두 정점을 연결하는 간선에 방향이 없다.

2. 방향 그래프 : 방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프이다. 

3. 가중치 그래프 : 가중치 그래프는 간선에 가중치(비용)가 할당된 그래프로, 두 정점을 이용할 때 비용이 든다.

4. 연결 그래프 : 무방향 그래프의 모든 정점 쌍이 항상 경로가 있는 그래프. 즉, 노드들이 하나도 빠짐없이 간선에 의해 연결된다. 대표적인 예로 트리(tree)가 있다.

5. 비연결 그래프 : 무방향 그래프에서 특정 정점 사이에 경로가 없는 그래프. 즉, 간선에 의해 연결되지 않은 노드도 있다.

6. 완전 그래프 : 그래프의 모든 정점이 서로 직접 연결되어 있다.

7. 순환 그래프 : 단순 경로에서 시작 정점과 도착 정점이 동일한 그래프

8. 비순환 그래프 : 사이클이 없는 그래프



그래프의 탐색

깊이 우선 탐색과 너비 우선 탐색이 있다. 자세한건 알고리즘 카테고리에서..



참고 및 출처

profile
이진이
프론트엔드 공부합니다. 블로그 이전: https://jinijana.tistory.com
이전 포스트

[프로그래머스] Lv.1 문자열 나누기

다음 포스트

[알고리즘] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

0개의 댓글