작성 : 202422040 김민석

2주차에는 가장 많이 활용되는 자료구조인 Graph에 대해서 학습한다. 또한 Graph 구조를 이용한 완전 탐색 방법인 DFS와 BFS를 학습한다.

코드는 c++ 언어를 기준으로 작성된다.

목차

1. Graph
2. DFS / BFS
3. Tree

1. Graph

이 목차에서 어려운 내용을 다루지는 않으니, 그래프의 정의를 알고 있다면 간단하게 읽고 넘어가도 좋다. (코드로 그래프를 구현하는 방법은 읽고 가도록 한다.)

그래프의 정의

• 그래프란 1개 이상의 vertices(또는 nodes)와 0개 이상의 edge의 집합이다.
• 그래프는 크게 무방향 그래프, 방향 그래프, 가중치 그래프로 구분할 수 있다. 각각의 내용은 위 그림을 통해 이해할 수 있다.

그래프 용어

정점 (vertex) : 노드(node)라고도 하며 위에서 알파벳으로 표현된 것을 말한다.

- 인접 정점 (adjacent vertex) : 정점에서 간선에 의해 연결되어 있는 정점이다.