[알고리즘] 그래프 -1

개념

인접 (adjacent)
- 그래프 G에 간선 (u,v)가 있을 때, 정점 u와 v는 인접해 있다고 함
부수(incident)
- 그래프 G에 간선 (u,v)가 있을 때, 간선은 정점 u와 v에 부수되어 있다고 함
차수(degree)
- 무방향그래프에서는 정점에 부수된 간선의 개수
- 방향그래프에서는 간선의 외향,내향에 따라 차수를 구별하여 외향차수, 내향차수라 함
경로(path)
- 간선으로 연결된 정점들의 순열
길이(depth)
- 경로상에 존재하는 간선의 개수
도달가능(reachable)
- 정점 u에서 v까지 경로 p가 존재할 경우 “도달가능”하다고 함
사이클(cycle)
- 시작정점과 끝정점이 같은 간선
부분그래프(subgraph)
- 그래프 G’의 모든 간선과 정점이 그래프 G의 부분집합일 경우, G’를 G의 부분그래프라 함
완전그래프(complete graph)
- 모든 정점들이 간선으로 연결된 그래프
이분그래프(bipartite graph)
- 모든 정점의 집합을 서로 소인 V1, V2로 나눌 때, V1집합 내부간의 간선은 존재하지 않고, V2집합 내부간 간선도 존재하지 않으며, 모든 간선이 V1집합과 V2집합만을 연결하는 그래프
숲(forest)
- 무사이클, 무방향 그래프
나무(tree)
- 연결된 무사이클, 무방향 그래프

깊이 우선 탐색 -> 최근의 주변 정점을 우선 방문
너비 우선 탐색 -> 주변 정점 중에서 오래된 것을 우선 방문

한 정점을 시작으로 매번 인접한 정점 중 한 곳으로 이동하며 탐색하는 방법
최근의 주변 정점을 우선으로 방문하는 탐색 방법
스택 구조를 사용해서 구현
- 현재 정점에 인접한 정점이 없어서 더 이상 탐색을 진행할 수 없으면 거꾸로 되돌아가면서 아직 탐색하지 않은 인접한 정점을 찾아서 탐색을 진행
처리 과정
1. 시작 정점을 스택에 삽입
2. 스택의 top에 있는 정점에 대한 주변 정점이 존재하면 그 중 하나의 정점을 스택에 삽입하고 방문한 정점으로 처리. 주변 정점이 없다면 스택의 top에 있는 정점을 제거
3. 스택에 더 이상의 정점이 없을 때까지 2의 과정을 반복
성능 및 특징
- 인접 리스트 : O( V + E )
- 인접 행렬 : (O V ^2^)
- 순환 알고리즘

시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법
- “거리” : 시작 정점으로부터 경로의 길이
주변 정점 중에서 가장 오래된 것부터 우선 방문하는 방법
큐를 사용하여 주변 정점을 관리

무사이클 방향 그래프에서 모든 간선이 한 방향으로만 향하도록 정점을 한 줄로 나열하는 것
깊이 우선 탐색을 활용하여 구함
- DFS를 수행하다가 더 이상 주변 정점이 없어서 되돌아갈 때, 스택에서 삭제되는 정점을 역순으로 나열하면 됨

정점 간의 연결 관계를 다루는 것
연결 성분
- 무방향의 그래프에서 임의의 두 정점간의 경로가 존재하는 최대 부분 그래프
- 너비 우선 탐색 또는 깊이 우선 탐식을 활용하여 구함

while (아직 탐색하지 않은 정점이 존재){
	탐색을 수행하다가 큐/스택이 비게 되면 그때까지 탐색한 정점들을 하나의 연결 성분으로 구성
}