자료구조 및 설계 실습1 소스코드 및 보고서:인접 리스트를 이용해 그래프를 저장

문제1)

인접 리스트를 이용해 그래프를 저장하는 프로그램인 리스팅 16.3에 한 개의 edge를 그래프에서 제거하는 함수를 작성하고 테스트하시오.

- 교재 16.3의 그래프 객체에 간선을 제거하는 함수 추가

- 그래프의 간선 제거 전 후를 확인

문제2)

a. 인접행렬을 이용해 그래프를 저장하는 프로그램인 리스팅 16.1에 너비우선탐색을 수행하는 메소드를 작성하시오

- 교재 16.1 그래프 객체에 너비우선탐색을 수행하는 함수 추가

- 교재 큐(Queue) 객체를 너비우선탐색에 이용

b. 16.1 그래프에 대해 너비우선탐색을 수행한 결과를 프린트하는 테스트 클래스를 작성하여 수행하시오.

- 너비우선탐색을 수행하는 동안 방문하는 정점을 출력

- 너비우선탬색 결과(트리)를 출력할 필요 없음

너비우선탐색(Breadth first search : BFS) : 레벨순서 순회 알고리즘을 그래프에 적용하기 위해 일반화시킨 것

너비우선탐색 알고리즘

입력 : 그래프 G=(V,E)와 최초 정점 v∈V

출력 : BFS 순서로 모든 정점을 가지고 있는 리스트 L

1. 지역 큐 Q와 정점의 출력 리스트 L을 초기화.

2. v를 방문했다고 마크하고 Q에 삽입

3. Q로 부터 x를 삭제하고 L에 삽입

4. x에 인접한 각각의 정점 y에 대해 단계 5를 반복

5. 만일 y를 아직 방문하지 않았다면, 이것을 방문했다고 마크하고 Q에 삽입

6. 마일 Q가 공백이 아니면, 단계 3으로 이동.

page hit