그래프 표현 방법과 알고리즘에 관한 퀴즈

그래프의 표현 방법에는 인접행렬, 인접리스트, 인접배열, 인접해시테이블 등이 있다. 인접행렬은 정점과 간선을 행렬로 표현하며, 인접리스트는 연결 리스트로 표현한다. 인접배열은 연결 배열로 표현하고, 인접해시테이블은 그래프가 큰 경우에 사용된다. 각 표현 방법은 장단점이 있으며, 선택은 그래프의 크기와 Edge의 개수에 따라 달라진다. 그래프에서 모든 정점을 방문하는 방법으로는 대표적으로 두 가지가 있다.그래프 알고리즘에 대한 핵심 포인트

1. 너비우선탐색(BFS)과 깊이우선탐색(DFS)은 그래프 알고리즘의 기본이다.
2. DFS와 BFS를 깊이 이해해야 좋은 그래프 알고리즘을 만들 수 있다.
3. BFS는 너비 우선으로 탐색하고, DFS는 깊이 우선으로 탐색한다.
4. BFS와 DFS는 모든 정점을 포함한 트리를 방문할 수 있다.
5. BFS의 수행 시간은 정점의 수(|V|)와 간선의 수(|E|)에 비례한다.
6. DFS의 수행 시간도 정점의 수(|V|)와 간선의 수(|E|)에 비례한다.
7. 최소신장 트리는 무향 연결 그래프에서 사용된다.
8. 최소신장 트리는 싸이클이 없는 연결 그래프이다.
9. 그래프 G의 최소신장트리는 간선의 합이 최소인 신장트리이다.
10. 프림 알고리즘은 그리디 알고리즘의 일종으로 최적해를 보장한다.
11. 프림 알고리즘의 수행 시간은 간선의 수(|E|)와 정점의 수(|V|)의 로그에 비례한다.
12. 크루스칼 알고리즘은 그리디 알고리즘으로 최소신장트리를 생성한다.