Graph란 무엇인가요?

그래프(graph)는 일련의 사물들과 그들 사이의 연결을 모델링하는 데이터 구조입니다. 사물들은 정점(vertices) (또는 노드)이라고 불리며, 연결은 간선(edges)이라고 불립니다.

그래프는 어디에나 있습니다. 소셜 네트워크는 그래프입니다 (사람은 정점이고, 친구 관계는 간선입니다). 도로 지도는 그래프입니다 (교차로는 정점이고, 거리는 간선입니다). 인터넷, 의존성 트리, 게임 맵 모두 그래프입니다.

이 과정에서 우리는 무방향(undirected) 그래프에 집중할 것입니다. 만약 간선이 u와 v를 연결한다면, v 또한 u에 연결됩니다. 방향성이 없습니다. 우리는 단순함을 유지하기 위해 정수(integers)를 정점 키로 사용할 것입니다.

내부적으로 우리는 그래프를 인접 리스트(adjacency list)로 저장할 것입니다. 이는 각 정점에서 해당 정점의 이웃 리스트로 연결되는 맵(map)입니다. 이렇게 하면 정점의 이웃을 찾는 작업이 단 한 번의 맵 접근으로 가능해지며, 이는 대부분의 그래프 알고리즘에 필요한 방식입니다.

우리가 Graph 클래스에 구축할 연산은 다음과 같습니다:

1. addVertex: 아직 간선이 없는 새로운 정점을 추가합니다.
2. addEdge: 두 정점을 연결합니다.
3. hasEdge: 두 정점이 연결되어 있는지 확인합니다.
4. getNeighbors: 정점의 이웃 리스트를 가져옵니다.
5. removeEdge: 두 정점의 연결을 끊습니다.
6. size: 그래프에 정점이 몇 개인지 셉니다.

이제 Graph 클래스를 만들어 봅시다!