DataStructure] C언어로 쉽게 풀어쓴 자료구조 10장 - 1

2학년 당시, 교재로 사용했던 책이다.

생능출판에서 나온 'C언어로 쉽게 풀어쓴 자료구조'라는 책의

10장 그래프 파트에 있었던 이론적인 문제들을 복습하면서 풀어봤는데, 풀면서 나온 자료를 올린다.

골치 아파하는 대학생들을 위해 조금의 참고자료가 되었으면 하지만,

이를 그대로 복사 붙여넣기 하는 것은 자기 실력 발전에 전혀 도움되지 않는다는 사실만을 알았으면 좋겠다.

 

혹시라도 답이 틀린 부분이 있거나, 의문이 남는 부분이 있다면 언제든지 댓글은 환영합니다.

 

 

 

1. 다음 중 그래프에 대한 설명으로 틀린 것은?
(4) 그래프에는 사이클이 존재하면 안 된다.

 

2. 인접 행렬 adj_mat[][]에서 어떤 정점 v의 진출 차수를 알고 싶으면 어떻게 하면 되는가?
(1) 인접 행렬의 v번째 행의 값들을 전부 더한다.

 

3. 인접 행렬 adj_mat[][]에서 어떤 정점 v의 진입 차수를 알고 싶으면 어떻게 하면 되는가?
(2) 인접 행렬의 v번째 열의 값들을 전부 더한다.

 

4. 인접 행렬이 {0, 1, 0, 0,}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0}이라면, 여기에 대응되는 인접 리스트를 그려라.

10장 - 4번

 

5. 최소 비용 신장 트리란?
그래프의 모든 정점들을 가장 적은 수의 간선과 비용으로 연결한 것.

 

6. 정점이 3개이고 간선이 3개가 있는 무방향 그래프에서 가능한 신장 트리의 개수는?
3개

 

7. 정점의 개수를 n, 간선의 개수를 e라고 할 때 인접 행렬에서 특정 정점의 차수를 계산하는 연산의 시간 복잡도는?
O(n)

 

8. 정점의 개수를 n, 간선의 개수가 e인 무방향 그래프를 인접 리스트로 표현하였을 경우, 인접 리스트 상의 총 노드의 개수는?
2e

 

9. 다음 중 큐를 사용하는 알고리즘은?
(2) 너비 우선 탐색(BFS)

 

10. 다음 방향의 그래프에 대하여 다음 질문에 답하라.
(1) 각 정점의 진입 차수와 진출 차수

0: 진입=1, 진출=3, 1: 진입=2, 진출=2, 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) 인접 행렬 표현

10장 - 10번.(3)

 

(4) 인접 리스트 표현

10장 - 10번.(4)

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

 

11. 정점 V={1,2,3,4,5,}이고, 간선 E={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,5>,<3,1>,<3,2>,<3,4>,<3,5>,<4,2>,<5,1>,<5,3>}으로 정의되는 방향 그래프를 그려라.

10장 - 11번

12. 방향 그래프 a가 nXn 인접 행렬을 사용하여 표현되어 있다.
(1) 주어진 정점의 진출 차수(out-degree)를 계산하는 함수를 작성하라. 진출 차수란 어떤 정점에서 출발하여 외부로 나가는 간선의 개수이다. 이 함수의 시간 복잡도는?

int calculateOutDegree(GraphType* g, int v)
{ 
	int i, degree=0; 
	for(i=0;in;i++)
		if(g->adj_mat[v][i]!=0) 
			degree++;
	return degree; 
} 

O(n)

 

(2) 주어진 정점의 진입 차수(in-degree)를 계산하는 함수를 작성하라. 진입 차수란 어떤 정점으로 들어오는 간선의 개수이다. 이 함수의 시간 복잡도는?

int calculateInDegree(GraphType* g, int v) 
{ 
	int i, degree=0; 
	for(i=0;in;i++) 
		if(g->adj_mat[i][v]!=0) 
			degree++; 
	return degree; 
}

O(n)

 

(3) 그래프 안에 있는 간선들의 개수를 계산하는 함수를 작성하라. 이 함수의 시간 복잡도는?

int calculateEdges(GraphType* g, int v) 
{ 
	int i, j, e=0; 
	for(i=0;in;i++) 
		for(j=0;jn;j++) 
			if(g->adj_mat[i][j]!=0) 
				e++; 
	return e; 
} 

O(n^2)

 

13. 만약 그래프가 인접 리스트로 표현되어 있다고 가정하고 12번 문제를 다시 풀어라.
(1)

int calculateOutDegree(GraphType* g, int v)
{ 
	int degree; 
	GraphNode* node=g->adj_list[v]; 
	while(node!=NULL) 
	{ 
		degree++; 
		node=node->link; 
	} 
	return degree; 
} 

O(e)

(2) 

int calculateInDegree(GraphType* g, int v) 
{ 
	int degree; 
	for(int i=0;in;i++)
	{ 
		node=g->adj_list[i]; 
		while(node!=NULL) 
		{ 
			if(node->vertex==v) 
				degree++; 
			node=node->link; 
		} 
	} 
	return degree++; 
} 

O(n+e)

(3)

int calculateEdges(GraphType* g, int v) 
{ 
	int e=0; 
	for(int i=0;in;i++) 
	{ 
		node=g->adj_list[i]; 
		while(node!=NULL) 
		{ 
			dgree++; 
			node=node->link; 
		} 
	} 
	return e; 
} 

O(n+e)

14. 만약 어떤 정점에 인접한 정점들만 알고 싶은 경우에, 인접 행렬 표현 방법과 인접리스트 표현 방법 중에서 어떤 것이 더 효율적인가?
인접 행렬은 O(n), 인접 리스트는 O(e/n)의 시간이 걸리는데, 통상적으로 e(Edges)는 정점의 숫자보다 적기 때문에 인접 리스트가 유리하다.

15. 3개, 4개, 5개의 정점으로 된 무방향 완전 그래프를 그려보라. n개의 정점을 갖는 완전 그래프의 간선의 개수가 n(n-1)/2인지를 확인하라.

10장 - 15번