Week3

Seungjae·2021년 3월 2일

TOOLS_스터디

목록 보기

3/10

Graph

Graph란 정점과 간선으로 이루어진 자료구조를 말합니다. 정점은 어떤 자료를 표현하며 간선은 정점들 사이 관계를 나타내기위해 사용됩니다.

Graph 용어

단순경로 : 특정 출발점에서 도착점으로 이동하는 동안 같은 정점을 최대 한 번만 방문한 경로.

사이클 : 출발점과 도착점이 같은 경우.

루프 : 한 정점을 기준으로 자기 자신으로 바로 연결되어 있는 간선.

연결 요소 : 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 하며, 다른 연결 요소에 속한 정점끼리는 경로가 존재하지 않음.

Graph 종류

양방향(무방향) 그래프 : 간선에 방향이 없는 그래프로, 두 정점 u,v 사이에 간선이 존재하는 경우 u->v v->u로 이동 가능. 즉 두 간선은 같은 간선.

완전 그래프 : 각 정점에서 자신을 제외한 모든 정점과 연결된 그래프로 간선의 갯수는 방향 그래프의 경우 V(V-1), 양방향 그래프는 V(V-1)/2.

다중 그래프 : 두 정점 사이에 간선이 여러 개 있는 그래프.

부분 그래프 : 어떤 그래프에서 정점(들)이나 간선(들)을 제외하며 만든 그래프.

이분 그래프 : 정점을 두 그룹으로 나누었을 때, 같은 그룹에 속한 정점끼리는 연결되어 있지 않은 그래프.

Graph 표현

1. 행렬을 이용하여 그래프 표현
-> a(i,j) = i번 정점에서 j번 정점으로 연결된 간선의 가중치(또는 연결여부)
-> 공간 복잡도 => O(V^2) (V는 정점)
-> 두 정점 사이의 연결 관계를 O(1)로 확인 가능
-> 특정 알고리즘을 위해 사용하거나 두 정점 사이의 연결 관계를 빠르게 계산하는 경우에 사용

2. 리스트를 이용하여 그래프를 표현
-> i번째 리스트에는 i번 정점과 연결되어 있는 간선들의 정보가 저장
-> 공간 복잡도 => O(E) (E는 간선)
-> 인접 행렬에 비해 특정 정점과 연결 되어 있는 모든 정점을 확인하는 작업을 빠르게 수행가능
-> 구현의 편의를 위해 리스트보다는 동적 배열을 주로 활용( ex) vector )
-> 대부분의 그래프 문제에서 사용

Search Algorithm

Search Algorithm은 그래프 상에서 특정 정점, 경로 등을 찾기 위해 사용하는 알고리즘입니다.

Search Algorithm 종류

1. DFS
-> 그래프를 방문 또는 탐색하는 방법 중 하나
-> 완전탐색이나 백트래킹 역시 일종의 DFS
-> 탐색의 횟수, 그래프의 최대 경로가 정해져 있거나 예측 가능한 경우 사용
-> DFS는 절대 최단 경로로 탐색을 진행X
-> 시간 복잡도 => 인접 행렬 O(V^2)
-> 시간 복잡도 => 인접 리스트 O(V+E)
-> 완전탐색, 백트래킹에서와 같이 이전 단계로 돌아가는 작업을 위해 stack사용
-> 재귀함수를 이용하는 경우 stack없이 구현 가능

2. BFS
-> 그래프를 방문 또는 탐색하는 방법 중 하나
-> 최단 거리, 최단 경로를 찾는 경우 간선의 가중치가 1 또는 0이 되어야 함
-> 가중치가 1 또는 0이 아닌 경우 우선순위큐를 이용할 수 있음
-> 시간 복잡도 => 인접 행렬 O(V^2)
-> 시간 복잡도 => 인접 리스트 O(V+E)