Data Structures in C (C언어로 쉽게 풀어쓴 자료구조) - 천인국 10장 연습문제

Posted by Patchman
2009.05.01 00:33 Univ Study/자료구조와 실습

1. (4)

2. (1)

3. (2)

4.

0-------1

1-------0->2->3

2-------1

3-------1

5. (4)

6. (3)

7. (2)

8. (2)

9. (2)

10.

(1) 각 정점의 진입차수와 진출차수

정점 0---- 진입차수 1, 진출차수 3

정점 1---- 진입차수 1, 진출차수 3

정점 2---- 진입차수 3, 진출차수 1

정점 3---- 진입차수 2, 진출차수 2

정점 4---- 진입차수 3, 진출차수 2

정점 5---- 진입차수 0, 진출차수 1

(2)

정점 0---- {1,2,3}

정점 1---- {2,3}

정점 2---- {4}

정점 3---- {0,4}

정점 4---- {1,2}

정점 5---- {4}

(3) 인접행렬

50

45

10

10

15

30

20

15

20

35

3

(4) 인접리스트

1

50

2

45

3

10

0--------->->->NULL

2

10

3

15

1--------->->NULL

4

30

2--------->NULL

0

20

4

15

3--------->->NULL

1

20

2

35

4--------->->NULL

4

3

5--------->NULL

(5) 사이클

경로 (0,1,3,0) 길이: 3

경로 (1,2,4,1) 길이: 3

경로 (0,2,4,1,3,0) 길이: 5

경로 (1,3,4,1) 길이: 3

11.

12.

(1) 진출 차수를 계산하는 함수

int calculate_out_degree(GraphType *g, int v)

{

int i, degree=0;

for(i=0;i<g->n;i++)

if( g->adj_mat[v][i] != 0 ) degree++;

return degree;

}

시간복잡도:

(2) 진입 차수를 계산하는 함수

int calculate_in_degree(GraphType *g, int v)

{

int i, degree=0;

for(i=0;i<g->n;i++)

if( g->adj_mat[i][v] != 0 ) degree++;

return degree;

}

시간복잡도:

(3) 간선들의 개수를 계산하는 함수

int calculate_num_edges(GraphType *g)

{

int r, c, edges=0;

for(r=0;r<g->n;r++)

for(c=0;c<g->n;c++)

if( g->adj_mat[r][c] != 0 )

edges++;

return edges;

}

시간복잡도:

13. 만약 그래프가 인접 리스트로 표현되어 있다고 가정하고 12번 문제를 다시 작성하라.(문제 오타 수정해주십시오.)

(1) 진출 차수를 계산하는 함수

int calculate_out_degree(GraphType *g, int v)

{

int degree=0;

GraphNode *node=g->adj_list[v];

while(node != NULL){

degree++;

node = node->link;

}

return degree;

}

시간복잡도:

(2) 진입 차수를 계산하는 함수

int calculate_in_degree(GraphType *g, int v)

{

int i, degree=0;

GraphNode *node;

for(i=0;i<g->n;i++){

node=g->adj_list[i];

while(node != NULL){

if( node->vertex == v ) degree++;

node = node->link;

}

return degree;

}

시간복잡도:

따라서 방향 그래프에서 진입차수를 구하는 것은 상당히 복잡해진다. 따라서 역인접 리스트(inverse adjacency list)라고 하는 별도의 리스트를 따로 만들기도 한다.

(3) 간선들의 개수를 계산하는 함수

int calculate_num_edges(GraphType *g)

{

int i, edges=0;

GraphNode *node;

for(i=0;i<g->n;i++){

node=g->adj_list[i];

while(node != NULL){

degree++;

node = node->link;

}

return edges;

}

시간복잡도:

14. 특정한 정점에 인접한 정점들을 알고 싶은 경우에는 인접행렬로 표현되어 있는 경우는 , 인접리스트로 표현되어 있는 경우는 평균적으로 의 시간이 걸린다. 일반적으로 하나의 정점에 연결된 간선의 개수는 정점의 개수보다는 적다. 따라서 인접 리스트 표현이 유리하다.

15. 3개의 정점을 가지는 무방향 완전 그래프->간선의 개수==3*2/2=3

3개의 정점을 가지는 무방향 완전 그래프->간선의 개수==4*3/2=6

19. 4개의 정점을 갖는 완전그래프에 대하여 깊이우선탐색과 너비우선탐색의 결과

깊이우선탐색: 0->1->2->3

너비우선탐색: 0->1->2->3

탐색의 결과는 인접리스트로 표현되었을 경우, 달라질 수 있다.

20. 그래프는 인접행렬로 표현되어 있다고 가정한다.

(1) 정점 3에서 출발하여 깊이 우선탐색했을 경우의 방문순서: 3->1->0->2->4->5->6->7->8->9

(2) 정점 6에서 출발하여 깊이 우선탐색했을 경우의 방문순서

6->5->3->1->0->2->4->7->8->9

(3) 정점 3에서 출발하여 너비 우선탐색했을 경우의 방문순서

3->1->4->5->0->2->6->7->8->9

(4) 정점 6에서 출발하여 너비 우선탐색했을 경우의 방문순서

6->5->7->3->8->9->1->4->0->2

22. 가능한 깊이우선 신장트리 나열

만약 그래프가 인접행렬로 표현되어 있고 깊이우선 탐색을 이용하여 신장트리를 만든다면 다음과 같은 신장트리만이 가능하다.

23. Kruskal 알고리즘

(0,1) 선택

(1,3) 선택

(2,4) 선택

(3,4) 선택

24. Prim 알고리즘

0번 정점 선택

1번 정점 선택

3번 정점 선택

4번 정점 선택

2번 정점 선택

26. 최단경로 알고리즘

단계

선택된 정점

found 배열

distance 배열

1

0

1,0,0,0,0,0

0,50,45,10,∞,∞

2

3

1,0,0,1,0,0

0,50,45,10,25,∞

3

4

1,0,0,1,1,0

0,45,45,10,25,∞

4

1

1,1,0,1,1,0

0,45,45,10,25,∞

5

2

1,1,1,1,1,0

0,45,45,10,25,∞

6

5

1,1,1,1,1,0

0,45,45,10,25,∞

31. 많은 위상정렬중에서 하나의 예는 다음과 같다.

cs1->cs2->cs3->cs5->cs4->cs6->cs7->cs8