보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오. 그래프의 깊이-우선 탐색 알고리즘 dfs()를 재귀적 버전이 아닌 반복적 버전으로 dfs_iter()를 작성하라 (Hint: 스택 사용) 5개의 정점을 갖는 완전 그래프를 인접 행렬로 초기화하고, 이 그래프에 dfs_iter()를 적용하라. 여러분은 프로그램을 실행시키고 테스트해야 한다. 다음은 main() 함수이다. 프로그램은 그래프의 정점을 방문한 순서대로 출력한다. int main() { // 인접 행렬 g를 초기화 // 깊이 우선 탐색 dfs_iter(g); return 0; }
보고서 #5- solution 다음은 dfs_iter()의 알고리즘이다. dfs_iter(g) { // g는 그래프 boolean visited[n ] = {false}; // 모든 정점을 방문하지 않은 것으로 초기화 // n은 그래프 g의 정점의 개수 stack <- createStack(); // 스택 생성 push(stack, 0); // 0은 방문 시작 정점 while (not isEmpty(stack)) do // 스택이 비어 있지 않으면 v<- pop(stack); if (visted[v] = false) then { // v를 이미 방문하지 않았으면 visited[v] <- true; for (v에 인접한 각 정점 w에 대해서) do if (visited[w] = false ) then // w가 이미 방문되지 않았으면 push (stack, w); end }