[알고리즘] 그래프

이번에 알아볼 알고리즘 중 자료구조는 그래프입니다!

그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다.

그 예시로 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들 등이 있습니다.

그래프 순회(임의의 한 정점에서 시작하여 모든 정점을 한 번씩 방문)에는 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

[알고리즘] 백트래킹 알고리즘

 

 

신장 트리

; 무방향 그래프 G(V,E)에서 E가 속한 간선들로 사이클을 포함하지 않으면서 + 모든 정점 V를 연결한 부분 그래프

- 간선의 수 = n-1

 

MST

(Minimum Spanning Tree, 최소 비용 신장 트리) ; 간선들의 가중치 합이 최소인 신장 트리 

Kruskal

; 결정의 순간마다 최선의 결정을 함으로써 최종적인 해답에 도달

a. 가중치 가장 작은 간선 선택 

b. 사이클이 형성되지 않게 a를 계속 반복(사이클이 형성된다면 선택 x)

 

Prim

; 트리 집합을 단계적으로 확장

a. 임의의 점 선택

b. 그 점에서 연결된 간선 중 가중치 가장 작은 간선 선택

c. 현재 연결된 간선 中 가중치 가장 작은 간선 선택

d. 사이클이 형성되지 않게 c를 계속 반복(형성된다면 선택 x)