[2014년] C++ 자료구조 6주차 연습문제

목차

1. 다음 용어를 설명하라.
2. 다음 그래프를 보고 물음에 답하시요.
3. 다음 그래프를 보고 물음에 답하시요.
4. 신장트리의 정의를 쓰시오.
5. 다음 그래프에서 3가지 알고리즘으로 최소비용신장트리를 구하고 그때의 최소비용을 구하라.
6. 다음 그래프에서 정점 ①로부터 모든 정점으로의 최단경로를 구하라
7. 다음 AOV network에서 위상순서를 3가지 이상 구하라.
8. 다음 AOE network의 임계경로를 구하라.
9. 위 8번의 network에서 간선<④,⑦>이 나타내는 작업과 간선<⑧,⑨>가 나타내는 작업의 earlist time과 latest time을 계산하라.

본문내용

1. 다음 용어를 설명하라. 이진탐색트리,스택,큐
1) subgraph (부분그래프)
- V(G)가 그래프의 정점들의 집합이고, E(G)가 그래프의 간선들의 집합이라고 할 때, V(G’)⊆V(G)이고, E(G’)⊆E(G)가 성립하는 그래프 G’을 부분그래프라고 한다.

2) adjacent (인접)
- 정점 u, v가 있고, (u,v)가 그래프 G의 한 간선 E(G) 집합에 속해있다면 u와 v는 인접한다고 한다.

3) connected (연결)
- 무방향 그래프 G에서 정점 u부터 v까지의 경로가 있다면 두 정점 u와 v는 연결되었다고 한다.

4) simple path (단순 경로)
- 한 경로 상에서 처음과 마지막을 제외한 모든 정점들이 서로 다를 때, 그 경로를 단순 경로라고 한다.

5) cycle (사이클)
- 처음과 마지막 정점이 같은 단순 경로

6) tree (트리)
- 그래프의 입장에서 보면 트리는 사이클이 없는 연결 그래프를 말한다.

7) in-degree (진입 차수)
- 방향 그래프에서 임의의 정점 v가 머리가 되는 간선들의 수를 정점 v의 진입 차수라 한다.

8) depth first search (깊이 우선 탐색)
- 출발 정점 v를 방문함으로써 시작. 다음으로 v에 인접하면서 아직 방문하지 않은 한 정점 w를 선택하여 이 w에서 다시 깊이 우선 탐색을 시작한다. 인접 정점들을 이미 모두 방문한 정점 u에 도달하면 마지막으로 방문한 정점 중 아직 방문하지 않은 인접 정점 w를 가지고 있는 정점까지 되돌아가서 정점 w로부터 깊이 우선 탐색을 다시 시작한다. 이러한 탐색은 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료된다.

9) articulation point (단절점)
- 그래프 G의 정점들 중에서 정점 v와 이 정점 v에 부속한 모든 간선들을 같이 삭제하면 최소한 두 개의 연결 요소를 만들게 하는 정점 v를 말한다.

참고 자료

없음