이번에 알아볼 알고리즘 중 자료구조는 그래프입니다!
그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다.
그 예시로 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들 등이 있습니다.
그래프 순회(임의의 한 정점에서 시작하여 모든 정점을 한 번씩 방문)에는 DFS와 BFS 등이 있습니다.
자료구조는 선형구조와 비선형 구조로 나뉘는데, 그래프는 그 중에서 비선형 구조입니다.
선형 구조
; 자료를 구성하고 있는 데이터들을 순차적으로 나열 시킨 형태
ex) 큐, 스택, 데큐
- 자료를 저장하고 꺼내는 것에 초점
비선형 구조
; 데이터가 계층적으로 구성된 형태
- 표현에 초점
ex) 트리, 그래프 / 컴퓨터의 폴더(폴더 속 폴더..)
그래프 용어
- 정점(=노드) ; 위치라는 개념
- 간선 ; 노드를 연결하는 선
- 인접 정점 ; 간선에 의해 직접 연결된 정점
- 정점의 차수 ; 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진입 차수 ; 방향그래프에서 외부에서 오는 간선의 수
- 진출 차수 ; 방향 그래프에서 외부로 향하는 간선의 수
- 사이클 ; 단순 경로의 시작 정점과 종료 정점이 동일한 경우
- 루프 ; 한 정점이 자기 자신으로의 경로를 가지는 경우
그래프 종류
- 방향 그래프 ; 간선에 방향이 있는 그래프
- 무방향 그래프 ; 간선에 방향이 없는 그래프
- 다중 그래프 ; 한 정점에서 다른 정점으로 가는 경로가 여러 개인 경우
- 정규 그래프 ; 모든 정점이 같은 차수를 가지는 그래프
- 완전 그래프 ; 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프 -> 간선의 수가 n(n-1)/2
- 동형 그래프 ; 2개의 그래프가 정점의 수, 간선의 수, 차수의 수가 모두 동일한 그래프
- 오일러 그래프 ; 모든 정점의 차수가 짝수인 그래프
- 해밀톤 그래프(Hamilton graph) ; 그래프의 모든 정점을 거쳐 시작 정점으로 cycle을 형성하며, 동일한 정점을 2번이상 지나지 않는 그래프
그래프의 표현
인접 행렬
- 선형 구조
- N개의 정점을 가진 그래프 G를 2차원 배열로 표시 ; 인접하면 1 / 아니면 0
- Dense Graph(밀도 있는 그래프) 표현할 때 적절
인접 리스트
- 비선형 구조
- n 개의 정점을 n개의 링크드리스트로 표현]
- Sparse Graph(희소 그래프) 표현할 때 적절
인접 다중 리스트
- 비선형 구조
- 노드들이 여러 리스트들을 공용하는 리스트
- 정점0 : E0 → E1
- 정점1 : E0 → E2 → E3
- 정점2 : E2 → E4
- 정점3 : E1 → E3 → E4
그래프의 운행(순회)
https://peter-coding.tistory.com/20
[알고리즘] 백트래킹 알고리즘
백트래킹(Back Tracking) ; 모든 경우의 수를 전부 고려하는 알고리즘 - 상태공간을 트리로 나타낼 수 있을 때 적합(트리 탐색 알고리즘) ▶ DFS(Depth-First Search) ; 깊이 우선 탐색 ; 최대한 깊이 내려간
peter-coding.tistory.com
신장 트리
; 무방향 그래프 G(V,E)에서 E가 속한 간선들로 사이클을 포함하지 않으면서 + 모든 정점 V를 연결한 부분 그래프
- 간선의 수 = n-1
MST
(Minimum Spanning Tree, 최소 비용 신장 트리) ; 간선들의 가중치 합이 최소인 신장 트리
Kruskal
; 결정의 순간마다 최선의 결정을 함으로써 최종적인 해답에 도달
a. 가중치 가장 작은 간선 선택
b. 사이클이 형성되지 않게 a를 계속 반복(사이클이 형성된다면 선택 x)
Prim
; 트리 집합을 단계적으로 확장
a. 임의의 점 선택
b. 그 점에서 연결된 간선 중 가중치 가장 작은 간선 선택
c. 현재 연결된 간선 中 가중치 가장 작은 간선 선택
d. 사이클이 형성되지 않게 c를 계속 반복(형성된다면 선택 x)
'알고리즘' 카테고리의 다른 글
| [알고리즘] 선형 리스트(Stack, Queue, Deque) (0) | 2022.06.06 |
|---|---|
| [알고리즘] 해시 (0) | 2022.06.06 |
| [알고리즘] 해싱(자료구조 기말고사 공부 정리) (0) | 2022.05.30 |
| [알고리즘] 탐색 (0) | 2022.05.29 |
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
| [알고리즘] 배열과 연결리스트 (0) | 2022.05.21 |
| [알고리즘] 정렬(삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬) (0) | 2022.05.16 |
| [알고리즘] 자료구조란 ? (0) | 2022.05.15 |
이번에 알아볼 알고리즘 중 자료구조는 그래프입니다!
그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다.
그 예시로 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들 등이 있습니다.
그래프 순회(임의의 한 정점에서 시작하여 모든 정점을 한 번씩 방문)에는 DFS와 BFS 등이 있습니다.
자료구조는 선형구조와 비선형 구조로 나뉘는데, 그래프는 그 중에서 비선형 구조입니다.
선형 구조
; 자료를 구성하고 있는 데이터들을 순차적으로 나열 시킨 형태
ex) 큐, 스택, 데큐
- 자료를 저장하고 꺼내는 것에 초점
비선형 구조
; 데이터가 계층적으로 구성된 형태
- 표현에 초점
ex) 트리, 그래프 / 컴퓨터의 폴더(폴더 속 폴더..)
그래프 용어
- 정점(=노드) ; 위치라는 개념
- 간선 ; 노드를 연결하는 선
- 인접 정점 ; 간선에 의해 직접 연결된 정점
- 정점의 차수 ; 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진입 차수 ; 방향그래프에서 외부에서 오는 간선의 수
- 진출 차수 ; 방향 그래프에서 외부로 향하는 간선의 수
- 사이클 ; 단순 경로의 시작 정점과 종료 정점이 동일한 경우
- 루프 ; 한 정점이 자기 자신으로의 경로를 가지는 경우
그래프 종류
- 방향 그래프 ; 간선에 방향이 있는 그래프
- 무방향 그래프 ; 간선에 방향이 없는 그래프
- 다중 그래프 ; 한 정점에서 다른 정점으로 가는 경로가 여러 개인 경우
- 정규 그래프 ; 모든 정점이 같은 차수를 가지는 그래프
- 완전 그래프 ; 서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프 -> 간선의 수가 n(n-1)/2
- 동형 그래프 ; 2개의 그래프가 정점의 수, 간선의 수, 차수의 수가 모두 동일한 그래프
- 오일러 그래프 ; 모든 정점의 차수가 짝수인 그래프
- 해밀톤 그래프(Hamilton graph) ; 그래프의 모든 정점을 거쳐 시작 정점으로 cycle을 형성하며, 동일한 정점을 2번이상 지나지 않는 그래프
그래프의 표현
인접 행렬
- 선형 구조
- N개의 정점을 가진 그래프 G를 2차원 배열로 표시 ; 인접하면 1 / 아니면 0
- Dense Graph(밀도 있는 그래프) 표현할 때 적절
인접 리스트
- 비선형 구조
- n 개의 정점을 n개의 링크드리스트로 표현]
- Sparse Graph(희소 그래프) 표현할 때 적절
인접 다중 리스트
- 비선형 구조
- 노드들이 여러 리스트들을 공용하는 리스트
- 정점0 : E0 → E1
- 정점1 : E0 → E2 → E3
- 정점2 : E2 → E4
- 정점3 : E1 → E3 → E4
그래프의 운행(순회)
https://peter-coding.tistory.com/20
[알고리즘] 백트래킹 알고리즘
백트래킹(Back Tracking) ; 모든 경우의 수를 전부 고려하는 알고리즘 - 상태공간을 트리로 나타낼 수 있을 때 적합(트리 탐색 알고리즘) ▶ DFS(Depth-First Search) ; 깊이 우선 탐색 ; 최대한 깊이 내려간
peter-coding.tistory.com
신장 트리
; 무방향 그래프 G(V,E)에서 E가 속한 간선들로 사이클을 포함하지 않으면서 + 모든 정점 V를 연결한 부분 그래프
- 간선의 수 = n-1
MST
(Minimum Spanning Tree, 최소 비용 신장 트리) ; 간선들의 가중치 합이 최소인 신장 트리
Kruskal
; 결정의 순간마다 최선의 결정을 함으로써 최종적인 해답에 도달
a. 가중치 가장 작은 간선 선택
b. 사이클이 형성되지 않게 a를 계속 반복(사이클이 형성된다면 선택 x)
Prim
; 트리 집합을 단계적으로 확장
a. 임의의 점 선택
b. 그 점에서 연결된 간선 중 가중치 가장 작은 간선 선택
c. 현재 연결된 간선 中 가중치 가장 작은 간선 선택
d. 사이클이 형성되지 않게 c를 계속 반복(형성된다면 선택 x)
'알고리즘' 카테고리의 다른 글
| [알고리즘] 선형 리스트(Stack, Queue, Deque) (0) | 2022.06.06 |
|---|---|
| [알고리즘] 해시 (0) | 2022.06.06 |
| [알고리즘] 해싱(자료구조 기말고사 공부 정리) (0) | 2022.05.30 |
| [알고리즘] 탐색 (0) | 2022.05.29 |
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
| [알고리즘] 배열과 연결리스트 (0) | 2022.05.21 |
| [알고리즘] 정렬(삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬) (0) | 2022.05.16 |
| [알고리즘] 자료구조란 ? (0) | 2022.05.15 |
