[C언어로 쉽게 풀어쓴 자료구조] 11장

01 다음의 그래프에서 가능한 신장 트리를 모두 나열하라.

02 아래의 네트워크에 대하여 Kruskal의 MST 알고리즘을 이용해서 최소비용 신장 트리가 구성되는 과정을 보여라.

03 앞의 네트워크에 대하여 Prim의 MST알고리즘을 이용해서 최소비용 신장 트리가 구성되는 과정을 보여라(A번 정점으로 시작할 것).

 

04 Prim의 함수에서 distance[]와 selected[]의 값을 출력하는 문장을 삽입하여 출력하여 보고 이들의 의미를 설명하라.

 

05 다음의 방향그래프에서 정점 0에서 다른 모든 정점까지의 최단 경로의 길이를 구하여라. 본문에서와 같이 다음의 표에 각 단계에서의 distance 배열의 값과 선택된 정점들을 나타내어라

단계	선택된 정점	found 배열	distance배열
1
2
...
n

06 5번의 그래프에 대하여 Floyd 알고리즘을 적용하고 배열 A의 내용을 매 단계마다 출력하라.

 

07 Dijkstra의 최단 경로 함수를 그래프가 인접 리스트로 표현되어 있다고 가정하고 재작성하라.

 

08 최단 경로 함수를 최단 경로의 길이 뿐만 아니라 그 경로까지 출력할 수 있도록 수정하라.

 

09 최단 경로 함수에서 distance[] 배열의 내용을 각 단계마다 출력하라. distance[]배열의 내용의 역할을 설명하라.

 

10 다음의 그래프에 대하여 위상 정렬을 적용하고 그 결과를 구하라.