DFS/BFS 알고리즘

소개글

1. DFS/BFS 알고리즘에 대해서 조사하시오.

결론은 주관적인 내용이 포함되어 있어서 삭제하였습니다.

목차

Ⅰ. 서론

Ⅱ. 본론
1. 그래프
2. 그래프 표현 방법
2.1 인접 행렬(Adjacency Matrix)
2.1.1 인접 행렬의 문제점
2.2 인접 리스트(Adjacency list)
2.2.1 인접 리스트의 장단점
3. 그래프 탐색 알고리즘
3.1 깊이 우선 탐색(Depth First Search)
3.1.1 깊이 제한(Depth bound)과 백트래킹(Backtracking)
3.1.2 스택을 이용한 깊이 우선 탐색의 절차
3.1.3 깊이 우선 탐색의 장단점
3.2 너비 우선 탐색(Breadth First Search)
3.2.1 큐를 이용한 너비 우선 탐색의 절차
3.2.2 너비 우선 탐색의 장단점

본문내용

서론
컴퓨터의 발전으로 인해 정치, 공학, 과학, 문화 등 많은 분야에서 데이터들이 증가하고 있다. 특히 트위터, 페이스북, 인스타그램, 카카오톡과 같은 소셜 네트워크 서비스의 대중화로 인해 이들이 쏟아내는 데이터는 급격히 증가하고 있다. 기업들은 이러한 사회 연결 망 분석을 통해 가치가 있는 정보를 추출하여 추천 시스템, 마케팅, 소비 패턴 파악 등 다양한 비즈니스 전략에 활용하고 있다. 이때, 일반적으로 사회 연결망은 그래프로 표현되며 이것은 현재 사회의 모든 정보들이 그래프로 표현된다는 것이기도 하다. 본문에서는 오늘날의 모든 것을 표현할 수 있는 그래프와 그래프를 탐색하는 알고리즘에 대해 살펴볼 것이다.
본론

1. 그래프
그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조로 정점과 간선들의 집합으로 구성되는데 G=(V, E)로 표시 한다. V(G)는 그래프G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 또한 정점의 차수는 그 정점에 부속된 간선들의 수이다. 그래프는 위상 순서, 최단 경로, 작업 네트워크 등에 이용된다.

참고 자료

최윤철, ICT 융합시대의 컴퓨터 과학, 생능출판사
김병조, 탐색 트리에 기반한 정보 수학 영재의 사고력 신장을 한 교수-학습 모형 개발 43쪽, 동의대학교 대학원 전산통계학과
이현진 조용연 김상욱, FlashGrap에서 너비우선탐색 알고리즘의 성능 개선 방안, 한국정보처리학회 2016년도 춘계학술발표대회
이세일, 타일맵에서 A* 알고리즘을 이용한 유닛들의 길찾기 방법 제안, 韓國컴퓨터情報學會論文誌
http://blog.eairship.kr/268?category=431859 알고리즘 4-1강. 깊이 우선 탐색(Depth First Search)
http://blog.eairship.kr/269?category=431859 알고리즘 4-2강. 너비 우선 탐색(Breadth First Search)
http://wanna-b.tistory.com/64?category=763448 그래프 탐색 알고리즘: DFS, BFS