[알고리즘]그래프(인접리스트, 깊이우선탐색, 너비우선탐색)

그래프란

7개의 다리를 한번씩 건너서 온 동네를 돌아다닐수 있는 방법을 찾다가 위대한 수학자 오일러가 고안

그래프의 정의

- 정점 : 하나의 위치를 가진 점

- 간선 : 하나의 길, 가중치, 방향을 가진 선

- 인접 : 점과 점이 간선으로 이웃되어 있는 경우

- 경로 : 하나의 점에서 다른 점을 간선을 따라 이동하는 길

- 사이클 : 하나의 점이 경로를 따라 2번 이상 거치는 경우

ex) A->B->C->A

- 연결성 : 무방향 그래프에서 두 정점 사이에 경로가 존재하는 경우

그래프 표현

정점끼리 인접 여부를 빠르게 알아야 한다면 인접 행렬

정점과 인선의 입력이 자주 발생한다면 인접 리스트

- 인접 행렬 그래프 : 모든 정보 저장

장점 : 직관적이고 구현이 쉬움

단점 : 불필요한 정보 저장으로 메모리 낭비와 NxN으로 메모리가 많이 필요함

인접해 있는 경우에는 1로 표시하고 인접하지 않으면 0 표시

- 인접 리스트 그래프 : 최소 값만 저장

장점 : 필요한 정보만 저장

단점 : 저장 하기 전에 확인 하는 과정이 필요함

방문했으면 상태를 방문으로하고 방문 하지 않았으면 미방문으로 상태 표시

그래프의 종류

- 무방향 그래프 : 간선에 방향이 없는 그래프

- 단방향 그래프 : 간선이 방향을 가 그래프

무방향/ 단방향

그래프 탐색 종류

- 깊이 우선 탐색(DFS-Depth FIrst Search) : 시작점부터 말단까지 깊게 확인하고 돌아오면서 이웃을 확인하는 탐색

- 너비 우선 탐색(BFS-Breadth First Search) : 시작점 주위 이웃들을 모두 확인 하고 다음 단계로 들어가는 탐색

다음에 확인해야 할 이웃을 큐에 넣고 확인 한 이웃은 큐에서 제거

- 위상 정렬(Topological Sort) : 진입 간선이 없는 정점을 리스트에 추가, 해당 정점과 진출 간선을 제거하는 탐색

2가지 조건 : 단뱡향 그래프, 사이클이 없는 그래프 내부

ex) A->B->F->C->D 

- 위상 정렬-깊이 우선 탐색 적용 : 가장 말단부터 헤드를 추가하면서 나오는 탐색

ex) A<-B<-F<-C<-D

소스는 깃허브에 올렸습니다.