보고서 #4 (1) (제출기한: 10/6) #1 다음 그래프 G에 대해서 답하시오. (2*5 = 10)

Presentation on theme: "보고서 #4 (1) (제출기한: 10/6) #1 다음 그래프 G에 대해서 답하시오. (2*5 = 10)"— Presentation transcript:

1 보고서 #4 (1) (제출기한: 10/6) #1 다음 그래프 G에 대해서 답하시오. (2*5 = 10)
G를 인접 행렬 m로 표현하라. a)의 인접 행렬 m을 전달받아서 인접 리스트로 변환하여 반환하는 알고리즘 graph_array2list(m) 을 작성하라. b)의 알고리즘을 C 언어를 이용하여 구현하고, 테스트하라. 인접 행렬과 인접 리스트의 표현은 다음과 같다. 인접행렬 표현 #define MAX 50 // 최대 정점의 개수 typedef struct graphType { int n; // 정점 개수 int adjMat[MAX][MAX]; // 인접 행렬 } graphType 2 1 3 4 5 6 7 8 인접리스트 표현 #define MAX 50 typedef struct graphNode { int vertex; // 정점 struct graphNode *link; } graphNode; typedef struct graphType { int n; // 정점 개수 graphNode * adjList[MAX]; } graphType;

2 보고서 #4 – solution (1) #1 다음 그래프 G에 대해서 답하시오. (2*5 = 10)
a)의 인접 행렬 m을 전달받아서 인접 리스트로 변환하여 반환하는 알고리즘 graph_array2list(m) 을 작성하라. graph_array2list(matrix_graphType mg, var list_graphType lg) integer i, j, n; graphNode *node; n <- mg.n; for i <- 1 to n do for j <- 1 to n do if mg.adjMat[i][j] = 1 then node = make_node(); node↑.vertex <- j; node ↑.link = NULL; add_first(lg.adjList[i], node); endif repeat end graph_array2list matrix_graphType mg = {…} // 인접 행렬 초기화 list_graphType lg; integer visited[mg.n] = {0}; // visited 배열 초기화 main() graph_array2list(mg, lg); // 인접 행렬을 인접 리스트로 변환 dfs(1); // 깊이-우선 탐색 // visited 배열 초기화 bfs(1); // 너비-우선 탐색 end main

3 보고서 #4 – solution (2) 그래프에서 정점 1을 시작으로 하여 깊이-우선 탐색하는 C 프로그램을 작성하고, 테스트하라. 프로그램의 알고리즘 복잡도는 무엇인가? 그 이유를 주라. 알고리즘 복잡도: dfs는 정점 v의 인접 리스트에 포함된 v의 인접 정점을 방문한다. 이 인접 리스트의 각 노드는 많아야 한번 방문되므로 복잡도는 O(e)이다. dfs(integer v) graphNode *node; integer vertex; visited[v] <- true; node <- lg. g.adjList[i]; while node != NULL do vertex <- node↑.vertex; if visited[vertex] != true then dfs(vertex); endif node <- node ↑.link; repeat end dfs

4 보고서 – solution (3) 그래프에서 정점 1을 시작으로 하여 너비-우선 탐색하는 C 프로그램을 작성하고, 테스트하라. 프로그램의 알고리즘 복잡도는 무엇인가? 그 이유를 주라. 알고리즘 복잡도: 각 정점은 큐에 한번 들어가므로 바깥 while 루프는 많아야 n번 반복. 안쪽 루프는 정점이 i이면 di번 반복. 따라서 전체로는 d1+d2+ …+dn번 반복되어 복잡도는 O(e)이다. bfs(integer v) graphNode *node; integer vertex, w; visited[v] <- true; init_queue(q); add_queue(q, v); while !is_empty(q) do vertex <- delete_queue(q); node <- lg. g.adjList[i]; while node != NULL do w <- node↑.vertex; if visited[w] != true then visited[w] <- true; add_queue(q, w); endif node <- node ↑.link; repeat end bfs