C++ - 10주차

DFS ( 깊이 우선 탐색)

- 재귀 함수로 구현 ( 스택 오버플로우에 유의해야함)

- 스택 자료구조 이용 

- 시간 복잡도 O(V+E)

- 단절점 찾기 , 단절선 찾기 , 사이클 찾기 , 위상 정렬

 

-> 인접 리스트: 한 번 방문한 노드를 다시 방문하면 안됨. 

-> 스택 : 후입선출 특성을 가짐

 

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 인접 리스트로 그래프 표현하기, 방문 배열 초기화 하기, 시작 노드 스택에 삽입하기

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의인접 노드를 다시 스택에 삽입하기

  pop을 수행해 노드를 꺼냄 . 꺼낸 노드의 인접 리스트의 인접 노드를 스택에 삽입해 배열 체크.

3. 스택 값이 없을 때 까지 반복하기

BFS ( 너비 우선 탐색)

- 시작노드 기준으로 가까운 노드를 먼저 방문하면서 탐색

- FIFO 탐색

- 큐 사용

- 최단 경로 보장

 

1. BFS 를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

  인접리즈트로 방문한 노드 체크 , 탐색할 땐 큐 사용

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입

3. 큐 자료구조에 값이 없을 때까지 반복하기 

 

2. 큐에 노드를 꺼낸 후 노드의 인접 노드를 다시 큐에 삽입하기

3.큐에 값이 없을 때까지 반복하기