10.그래프
- 최초 등록일
- 2018.05.02
- 최종 저작일
- 2018.05
- 16페이지/ MS 워드
- 가격 1,000원
목차
1. 인접 행렬 adj_mat[][]에서 어떤 정점 v의 진출 차수를 알고 싶으면 어떻게 하면 되는가?
2. 인접 행렬이 {0,1,0,0}, {1,0,1,1}, {0,1,0,0}, {0,1,0,0} 이라면 여기에 대응되는 인접 리스트를 그려라.
3. 정점이 3개이고 간선이 3개가 있는 무 방향 그래프에서 가능한 신장 트리의 개수는?
4. 정점의 개수를 n, 간선의 개수가 e인 무 방향 그래프를 인접 리스트로 표현하였을 경우, 인접 리스트 상의 총 노드의 개수는?
5. 다음의 방향 그래프에 대하여 다음 질문에 답하라.
6. 방향 그래프 a가 n X n 인접 행렬을 사용하여 표현되어 있다.
7. 만약 어떤 정점에 인접한 정점들 만을 알고 싶은 경우에, 인접 행렬 표현 방법과 인접 리스트 표현 방법 중에서 어떤 것이 더 효율적인가?
8. 하드 디스크에 파일로 그래프의 인접 행렬이 저장되어 있다고 가정하고 다음과 같은 함수를 작성하라. 그래프 파일의 형식은 다음과 같다.
9. 그래프 추상 데이터 타입에서 간선을 삭제하는 연산인 delete_edge 연산을 인접 행렬과 인접 리스트에 대하여 각각 구현하라.
10. 다음의 그래프에 대하여 답하라. 그래프는 인접 행렬로 표현되어 있다고 가정한다.
11. 다음의 그래프에서 가능한 깊이 우선 신장 트리를 모두 나열하여라.
12. 문제 23의 네트워크에 대하여 prime의 MST 알고리즘을 이용해서 최소 비용 신장 트리가 구성되는 과정을 보여라. (정점은 0번)
13. 다음의 방향 그래프에서 정점 0에서 다른 모든 정점까지의 최단 경로의 길이를 구하여라. 본문에서와 같이 다음의 표에 각 단계에서의 distance 배열의 값과 선택된 정점들을 나타내어라.
14. Dijkstra의 최단 경로 함수를 최단 경로의 길이뿐만 아니라 그 경로까지 출력할 수 있도록 수정하라.
본문내용
6. 정점이 3개이고 간선이 3개가 있는 무 방향 그래프에서 가능한 신장 트리의 개수는?
답 : 3개
: 정점이 3개이고 간선이 3개인 그래프는 삼각형 모양의 사이클 트리와 같다. 각 정점의 데이터를 1, 2, 3이라고 하였을 때 정점이 3개, 간선이 n-1개로 2개인 신장 트리는 1과2, 2와3, 1과3을 잇는 트리로 총 3개가 가능하다.
8. 정점의 개수를 n, 간선의 개수가 e인 무 방향 그래프를 인접 리스트로 표현하였을 경우, 인접 리스트 상의 총 노드의 개수는?
답 : 2e개
: 무 방향 그래프는 방향이 없이 두 정점이 서로를 연결하고 있으므로 이를 인접 리스트로 표현하면 정점이 n개, 간선이 e개 일 때 n개의 연결리스트와 헤드 포인터, 2e개의 노드를 가진다.
10. 다음의 방향 그래프에 대하여 다음 질문에 답하라.
(1) 각 정점의 진입 차수와 진출 차수
* 진입 차수 = 외부에서 오는 간선의 수
* 진출 차수 = 외부로 향하는 간선의 수
참고 자료
없음