📝그래프의 개념
그래프에 대해 학습하다보니 그래프라는 자체가 정말 많은 개념들을 포함하고 있다는 것을 알게 되었다. 트리, 힙 구조들도 올라가보면 그래프에서 시작되는 개념이다.
-
그래프는 정점(Vertex)와 정점을 연결하는 간선(edge)의 집합으로 이루어져있다.
-
그래프는 연결되어있는 정점들간의 관계를 표현
그래프의 종류
- 무방향 : 연결하는 간선에 방향이 없음
- 방향 : 간선에 방향이 존재
- 완전 : 정점들이 모두 연결되어 간선의 수가 최대
- 가중치 : 간선에 가중치가 존재
- 부분 : 기본 그래프에 일부 정점이나 간선이 빠져있는
- 연결 : 모든 정점들이 연결되있어 떨어져있는 정점이 없음
- 단절 : 떨어져있는 정점이 존재
🤷♂️그래프는 어디에 사용될까?
- 도시간의 경로
- 소셜 네트워크 유저(유저-정점)
그래프 탐색
- DFS 깊이우선탐색
노드들의 자식들을 위주로 탐색을 진행하며 더 이상 자식이 없을 때까지 탐색을 진행한다. 보통 스택or재귀를 사용하여 탐색을 한다. [11724번]에서 사용한다.
#위에서 아래로 탐색
#왼쪽으로 가나 오른쪽으로 가냐는 상관없음
#가야할 노드, 방문한 노드를 기준으로 탐색
- BFS 넓이우선탐색
같은 레벨의 노드 형제 노드들을 우선으로 탐색한다.
큐를 활용해 구현한다.
문제풀이
- [S2]11724] 연결 요소의 개수
- [S1]1446] 지름길
- [G4]14502] 연구소
