[알고리즘] 12. 그래프

공부한 날짜: 2021. 11. 02

 

1. 그래프 

 

• 그래프: 정점의 모음과 간선의 모음의 결합

인접,이웃관계: 간선으로 연결되어 있는 두 정점이 이루는 관계

길이: 정점과 정점 사이의 간선의 수

사이클: 정점 하나를 두번 이상 거치는 경로

종류: 방향성 그래프(Directed Graph), 무방향성 그래프(Undirected Graph)

연결성: 그래프 내의 각 정점들이 모든 정점들과 연결되어 있는 경우

간선: 정점과 정점이 인접관계에 있음을 나타내는 존재

 

• 정점사이의 인접 관계를 표현하는 방법(인접 행렬/리스트)

 

(1) 인접 행렬(Adjacency Matrix)

:정점끼리의 인접 관계를 나타내는 행렬

행렬이 대칭이면 무방향 그래프, 대칭이 아니면 방향 그래프
장점: 정점간의 인접 여부 빠르게 알 수 있음

단점: 메모리를 많이 차지함(크기 정점 x N^2)

 

(2) 인접 리스트 (Adjacancy List)

:정점끼리의 인접 관계를 나타내는 리스트, 모든 정점의 목록을 리스트로 관리하도록 한다. 

장점: 사용하는 메모리의 양 적음

단점: 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차탐색을 해야함

 

-> 어느 것이 더 낫다라고 말할 수는 없고, 그때그때 상황에 따라 최적인 방법으로 사용하는 것이 중요하다

 

-그래프구현

 

 

 

2. 그래프 순회

-그래프를 순회하는 방법:  깊이 우선 방식/ 너비 우선 방식

 

(1) 깊이 우선 방식-> 그래프 정렬 알고리즘 

:"더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"의 원칙으로 그래프 내의 정점을 방문하는 알고리즘, 스택을 이요함 

동작방식: 

ㄱ. 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시

ㄴ. not visited 인접 정렬을 시작 정점으로 정하고, 깊이 우선 탐색 시작( ㄱ단계 반복)

ㄷ. 정점에 더이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 ㄴ단계 수행

ㄹ. 이전 정점으로 돌아가도 더 이상 방문할 이웃이 없다면 그래프의 모든 정점을 모두 방문했다는 뜻 -> 탐색 종료

 

(2) 너비 우선 방식 -> 최단 경로 찾기 알고리즘

:"꼼꼼하게 좌우를 살피며 다니자" (깊이가 1인 정점을 모두 방문하고, 그다음 깊이가 2인 정점 모두 방문,,,), 큐를 이용함 

ㄱ. 시작 정점을 'visted'로 표시하고 큐에 삽입(enqueue)

ㄴ. 큐로부터 정점을 제거(dequeue). 제거한 정점이 이웃하고 있는 인접 정점 중 아직 방문하지 않은 곳들을 '방문했음'으로 표시하고 큐에 삽입

ㄷ. ㄴ단계 반복하다 큐가 비게되면 종료