IT, FIRE, License and Daily life

<해싱(hashing)>

산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다.

[검색 방법]
키 값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블로 바로 이동한다. 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 검색 실패

[해싱 함수(hashing function)]
키 값을 원소의 위치로 변환하는 함수 

[해시 테이블(hash table)]
해싱 함수에 의해서 계산된 주소의 위치에 항목을 저장한 표

데이터를 담을 그룻(테이블)을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것을 말하며 , 해쉬 테이블은 여유공간이 많아야 충분한 제 성능을 발휘할 수 있다.

[용어]

1. 충돌(collision)
- 서로 다른 키 값에 대해서 해싱 함수에 의해 주어진 버킷 주소를 같은 경우
- 충돌이 발생한 경우에 비어있는 슬롯에 동거자 관계로 키 값 저장 

2. 동거자 (synonym)
- 서로 다른 키 값을 가지지만 해싱 함수에 의해서 같은 버킷에 저장된 키 값들 

3. 오버플로우
- 버킷에 비어있는 슬롯이 없는 포화 버킷 상태에서 충돌이 발생하여 해당 버킷에 키 값을 저장할 수 없는 상태

<해싱 함수 종류>

1. 제산 함수

나머지 연산자 mod를 사용하는 방법으로서 키값k를 해시 테이블의 크기 M으로 나눈 나머지를 해시 주소로 사용한다.

h(k) = k mod M

2. 승산 함수

곱하기 연산을 사용하는 방법인데, 키 값k와 정해진 실수 a를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기 M과 곱하여 그 정수값을 주소로 사용한다.

3. 접지 함수

키의 비트수가 해시 테이블 인덱스의 비트수보다 큰 경우에 주로 사용하는 방법이다. 키값 k가 있을 때 해시 테이블 인덱스의 비트수와 같은 크기로 분할한 후 분할된 부분을 모두 더하여 해시 주소를 만든다.

① 이동 접지 함수
각 분할 부분을 이동시켜서 오른쪽 끝자리가 일치하도록 맞추고 더하는 방법
예) 해시 테이블 인덱스가 3자리이고 키 값 k가 123 123 123 12인 경우

② 경계 접지 함수
분할된 각 경계를 기준으로 접으면서 서로 마주보도록 배치하고 더하는 방법
예) 해시 테이블 인덱스가 3자리이고 키 값 k가 123 123 123 12인 경우

Copyrightⓒ2014 By 한빛아카데미(주)

<색인 순차 검색(index sequential search)>
​

정렬되어있는 자료에 대한 인덱스 테이블(index table)을 추가로 사용하여 탐색 효율을 높인 검색 방법이다. 

[인덱스 테이블]
배열에 정렬되어있는 자료 중에서 일정한 간격으로 떨어져있는 원소들을 저장한 테이블이다. 자료가 저장되어있는 배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때, 배열에서 n/m간격으로 떨어져있는 원소와 그의 인덱스를 인덱스 테이블에 저장한다. 

[검색 방법]
indexTable[i].key ≤ key < indexTable[i+1].key를 만족하는 i를 찾아서 배열의 어느 범위에 있는지를 먼저 알아낸 후에 해당 범위에 대해서만 순차 검색 수행

예)

검색 대상 자료 : {1, 2, 8, 9, 11, 19, 29}
크기가 3인 인덱스 테이블 작성
인덱스 테이블에서 먼저 탐색키를 검색하여 검색 범위를 확인하고, 해당 범위에 대해서만 순차 검색 실행

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<순차 검색(sequential search, 선형 검색(linear search)> 

일렬로 된 자료를 처음부터 마지막까지 순서대로 검색하는 방법이다. 가장 간단하고 직접적인 검색 방법이며, 배열이나 연결 리스트로 구현된 순차 자료 구조에서 원하는 항목을 찾는 방법이다.

1. 정렬되지 않은 순차자료구조에서의 순차 검색
[검색 방법]
① 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다.
② 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다.
③ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패
순차 검색 예) 검색 성공의 경우

예) 검색 실패의 경우

[코드]

2. 정렬되어 있는 순차자료구조에서의 순차 검색
[검색 방법]
순서대로 검색하면서 키 값을 비교하여, 원소의 키 값이 찾는 키 값보다 크면 찾는 원소가 없는 것이므로 더 이상 검색을 수행하지 않고 검색종료
정렬되어있는 자료에 대한 순차 검색 예)

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<합병 정렬(Merge Sort)>

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법이다. 부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 후에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법을 사용한다.

[용어]

1. 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할한다

2. 정복(conquer) : 부분집합의 원소들을 정렬한다.
부분집합의 크기가 충분히 작지 않으면 순환호출을 이용하여 다시 분할 정복 기법을 적용한다.

3. 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 결합한다.

예)

정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 병합 정렬 방법으로 정렬하는 과정을 살펴보자.
① 분할 단계 : 정렬할 전체 자료의 집합에 대해서 최소 원소의 부분집합이 될 때까지 분할작업을 반복하여 1개의 원소를 가진 부분집합 8개를 만든다.

② 병합단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다. 8개의 부분집합이 1개로 병합될 때까지 반복한다.

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<삽입 정렬(insert sort)>

정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 

정렬할 자료를 두 개의 부분집합 S와 U로 가정
부분집합 S : 정렬된 앞부분의 원소들
부분집합 U : 아직 정렬되지 않은 나머지 원소들 

정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.
삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분집합 U가 공집합이 되면 삽입 정렬이 완성된다. 

[삽입 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 삽입 정렬 방법으로 정렬하는 과정을 살펴보자. 

초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고, 나머지 원소들은 정렬되지 않은 원소들의 부분 집합 U로 생각한다.

S={69} , U={10, 30, 2, 16, 8, 31, 22}

① U의 첫 번째 원소 10을 S의 마지막 원소 69와 비교하여 (10 < 69) 이므로 원소 10은 원소 69의 앞자리가 된다. 더 이상 비교할 S의 원소가 없으므로 찾은 위치에 원소 10을 삽입한다.
S={10, 69} , U={30, 2, 16, 8, 31, 22}

② U의 첫 번째 원소 30을 S의 마지막 원소 69와 비교하여 (30 < 69)이므로 원소 69의 앞자리 원소 10과 비교한다. (30 > 10) 이므로 원소 10과 69 사이에 삽입한다.
•S={10, 30, 69} , U={2, 16, 8, 31, 22}

③ U의 첫 번째 원소 2를 S의 마지막 원소 69와 비교하여 (2 < 69) 이므로 원소 69의 앞자리 원소 30과 비교하고, (2 < 30) 이므로 다시 그 앞자리 원소 10과 비교하는데, (2 < 10) 이면서 더 이상 비교할 S의 원소가 없으므로 원소 10의 앞에 삽입한다.
•S={2, 10, 30, 69} , U={16, 8, 31, 22}

④ 이런 작업을 반복한다.

⑤ U의 첫 번째 원소 22를 S의 마지막 원소 69와 비교하여 (22 < 69)이므로 그 앞자리 원소 31과 비교한다.
(22 < 31) 이므로 그 앞자리 원소 30과 비교하고,
(22 < 30) 이므로 다시 그 앞자리 원소 16과 비교하여,
(22 > 16) 이므로 원소 16과 30 사이에 삽입한다.
•S={2, 8, 10, 16, 22, 30, 31, 69} , U={}

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<퀵 정렬(quick sort)>

분할 정렬 방법이며, 정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.
왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.

기준 값 : 피봇(pivot)이란?
일반적으로 전체의 원소 중에서 가운데에 위치한 하나의 원소를 골라서 선택 

퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성한다.
1. 분할(divide)
정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할하기
2. 정복(conquer)
부분 집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분 집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬하기.
부분 집합의 크기가 1 이하로 충분히 작지 않으면 순환호출을 이용하여 다시 분할.

[퀵 정렬 수행 방법]
- 부분 집합으로 분할하기 위해서 L과 R을 사용
① 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇 보다 크거나 같은 원소를 찾아 L로 표시
② 오른쪽 끝에서 왼쪽으로 움직이면서 피봇 보다 작은 원소를 찾아 R로 표시
③ L이 가리키는 원소와 R이 가리키는 원소를 서로 교환한다.
- L와 R이 만나게 되면 피봇과 R의 원소를 서로 교환하고, 교환한 위치를 피봇의 위치로 확정한다.
- 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분 집합과 오른쪽 부분 집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데 모든 부분 집합의 크기가 1 이하가 되면 퀵 정렬을 종료한다.

[퀵 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 퀵 정렬 방법으로 정렬하는 과정을 살펴보자. 

원소의 개수가 8개이므로 네 번째 자리에 있는 원소 2를 첫 번째 피봇으로 선택하고 퀵 정렬 시작.

① 원소 2를 피봇으로 선택하고 퀵 정렬 시작.

L이 오른쪽으로 이동하면서 피봇 보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾는다.
L은 원소 69를 찾았지만, R은 피봇 보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 된다.
L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 2의 위치를 확정한다.

② 피봇 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.
오른쪽 부분 집합의 원소가 7개 이므로 가운데 있는 원소 16을 피봇으로 선택.

L이 찾은 30과 R이 찾은 8을 서로 교환한다.

현재 위치에서 L과 R의 작업을 반복한다.
L은 원소 69를 찾았지만, R은 피봇 보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 된다. L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 16의 위치를 확정한다.

③ 이런식으로 반복수행한다.

④ 피봇 30의 확정된 위치에서의 왼쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.
오른쪽 부분 집합의 원소 2개 중에서 원소 31을 피봇으로 선택한다.

L은 오른쪽으로 이동하면서 원소 31을 찾고, R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾다가 못 찾은 채로 원소 31에서 L과 만난다.
L과 R이 만났으므로 피봇과 교환하는데 R의 원소가 피봇이므로 결국 제자리가 확정된다.

피봇 31의 오른쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않는다. 이것으로써 전체 퀵 정렬이 모두 완성되었다.

퀵 정렬을 분석해보자.

[메모리 사용공간]
n개의 원소에 대하여 n개의 메모리 사용 

[연산 시간]
1. 최선의 경우
- 피봇에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
2. 최악의 경우
- 피봇에 의해 원소들을 분할하였을 때 1개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우

평균 시간 복잡도 : O(n log2n)

같은 시간 복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 더 빨리 실행되어 실행 시간 성능이 좋은 정렬 방법임.

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<버블 정렬(bubble sort)>

​인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.
첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(bubble) 정렬이라 한다. 

[버블 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 버블 정렬 방법으로 정렬하는 과정을 살펴보자.

① 인접한 두 원소를 비교하여 자리를 교환하는 작업을 첫 번째 원소부터 마지막 원소까지 차례로 반복하여 가장 큰 원소 69를 마지막 자리로 정렬.

② 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 31을 끝에서 두 번째 자리로 정렬.

③ 이과정을 반복 수행한다. 

④ 버블 정렬을 수행하여 나머지 원소 중에서 가장 큰 원소 8을 끝에서 일곱 번째 자리로 정렬.

버블 정렬을 분석해보자.

[메모리 사용공간]
n개의 원소에 대하여 n개의 메모리 사용 

[연산 시간]
1. 최선의 경우 : 자료가 이미 정렬되어있는 경우
- 비교횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
- 자리교환횟수 : 자리교환이 발생하지 않음
2. 최악의 경우 : 자료가 역순으로 정렬되어있는 경우
- 비교횟수 : i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
−자리교환횟수 : i번째 원소를 (n-i)번 교환하므로, n(n-1)/2 번
평균 시간 복잡도는 O(n2)이 된다.

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<선택 정렬(selection sort)>

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 

[수행 방법]
1. 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다.
2. 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환한다.
3. 그 다음에는 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환한다.
4. 이 과정을 반복하면서 정렬을 완성한다.

ex) 정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 선택 정렬 방법으로 정렬하는 과정을 보여라.

① 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69와 자리 교환

② 두 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 10과 자리 교환

③ 이런식으로 반복한다.

④ 일곱 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 31을 선택하여 기준 위치에 있는 원소 31과 자리 교환. (제자리)

선택 정렬을 분석해보자.

1. 메모리 사용공간 - n개의 원소에 대하여 n개의 메모리 사용
2. 비교횟수
1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교
2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교
i 단계 : i 번째 원소를 기준으로 n-i개의 원소 비교

전체 비교횟수는 n(n-1)/2이다. 

즉, 어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n2)이 된다.

[선택 정렬 코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<정렬(sort)>

​2개 이상의 자료를 작은 것부터 큰 것 순서의 오름차순(ascending)이나 큰 것부터 작은 것 순서의 내림차순(descending)으로 재배열하는 것
키 - 자료를 정렬하는데 사용하는 기준이 되는 특정 값 

[정렬의 예]

<실행 방법에 따른 분류> 

1. 비교식 정렬(comparative sort)
비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법
2. 분산식 정렬(distribute sort)
키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법

<내부 정렬(internal sort)>

​정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨 

[내부 정렬 방식]
- 교환 방식 : 키를 비교하고 교환하여 정렬하는 방식 (선택 정렬, 버블 정렬, 퀵 정렬)
- 삽입 방식 : 키를 비교하고 삽입하여 정렬하는 방식(삽입 정렬, 쉘 정렬)
- 병합 방식 : 키를 비교하고 병합하여 정렬하는 방식 (2-way병합, n-way병합)
- 분배 방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식 (기수 정렬)
- 선택 방식 : 이진 트리를 사용하여 정렬하는 방식 (히프 정렬, 트리 정렬) 

<외부 정렬(external sort)>

​정렬할 자료를 보조 기억장치에서 정렬하는 방식
대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬 가능 

[외부 정렬 방식]

- 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 정렬 방식 (2-way 병합, n-way 병합)

Copyrightⓒ2014 By 한빛아카데미(주)

<깊이 우선 탐색(depth first search : DFS)>

DFS란 스택을 이용하여 그래프를 탐색해 나가는 방법으로써 가능한 깊이 vertex를 들어간뒤 특정 vertex에서 더이상 갈곳이 없으면 그 vertex를 체크한뒤 다시 올라가서 갈 수 있는 모든 vertex를 탐색해나가는 기법이다.

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법.
가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용.

[깊이 우선 탐색의 수행 순서]

⑴ 시작 정점 v를 결정하여 방문한다.
⑵ 정점 v에 인접한 정점 중에서
① 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 ⑵를 반복한다.
② 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 ⑵를 반복한다.
⑶ 스택이 공백이 될 때까지 ⑵를 반복한다.

[알고리즘]

ex)

① 정점 A를 시작으로 깊이 우선 탐색을 시작

visited[A]←true;

② 정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push 하고, 인접정점 B와 C 중에서 오름차순에 따라 B를 선택하여 탐색을 계속한다.

push(stack, A);
visited[B]←true;
B 방문;

③ 정점 B에 방문하지 않은 정점 D, E가 있으므로 B를 스택에 push 하고, 인접정점 D와 E 중에서 오름차순에 따라 D를 선택하여 탐색을 계속한다.

push(stack, B);
visited[D]←true;
D 방문;

④ 정점 D에 방문하지 않은 정점 G가 있으므로 D를 스택에 push 하고, 인접정점 G를 선택하여 탐색을 계속한다.

push(stack, D);
visited[G]←true;
G 방문;

⑤ 정점 G에 방문하지 않은 정점 E, F가 있으므로 G를 스택에 push 하고, 인접정점 E와 F 중에서 오름차순에 따라 E를 선택하여 탐색을 계속한다.

push(stack, G);
visited[E]←true;
E 방문;

⑥ 정점 E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push 하고, 인접정점 C를 선택하여 탐색을 계속한다.

push(stack, E);
visited[C]←true;
C 방문;

⑦ 정점 C에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 E에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑧ 정점 E는 방문하지 않은 인접정점이 없으므로, 다시 스택을 pop 하여 받은 정점 G에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑨ 정점 G에 방문하지 않은 정점 F가 있으므로 G를 스택에 push 하고, 인접정점 F를 선택하여 탐색을 계속한다.

push(stack, G);
visited[F]←true;
F 방문;

⑩ 정점 F에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 G에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑪ 정점 G에서 방문하지 않은 인접정점이 없으므로, 다시 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 D에 대해서 방문하지 않은 인접정점이 있는지 확인한다.

pop(stack);

⑫ 모두 pop을 한다.

⑬ 현재 정점 A에서 방문하지 않은 인접 정점이 없으므로 마지막 정점으로 돌아가기 위해 스택을 pop하는데, 스택이 공백이므로 깊이 우선 탐색을 종료한다.

2. 너비 우선 탐색(breadth first search : BFS)
−BFS란 큐를 이용하며 그래프를 탐색해 나가는 방법으로, 탐색에 대한 특징은 너비 우선 탐색은 깊이가 1인 모든 정점을 방문하고 나서, 그 다음에는 깊이가 2인 모든 정점을, 깊이가 3인 모든 정점을 방문하는 식으로 계속 방문하다가 더이상 방문할 곳이 없으면 탐색을 마치는 기법이다.

Copyrightⓒ2014 By 한빛아카데미(주)