소개글
DFS/BFS 알고리즘에 대해서 조사하시오.에 대한 자료입니다.
본문내용
1. DFS/BFS 알고리즘에 대해서 조사하시오.
서론
컴퓨터의 발전으로 인해 정치, 공학, 과학, 문화 등 많은 분야에서 데이터들이 증가하고 있다. 특히 트위터, 페이스북, 인스타그램, 카카오톡과 같은 소셜 네트워크 서비스의 대중화로 인해 이들이 쏟아내는 데이터는 급격히 증가하고 있다. 기업들은 이러한 사회 연결 망 분석을 통해 가치가 있는 정보를 추출하여 추천 시스템, 마케팅, 소비 패턴 파악 등 다양한 비즈니스 전략에 활용하고 있다. 이때, 일반적으로 사회 연결망은 그래프로 표현되며 이것은 현재 사회의 모든 정보들이 그래프로 표현된다는 것이기도 하다. 본문에서는 오늘날의 모든 것을 표현할 수 있는 그래프와 그래프를 탐색하는 알고리즘에 대해 살펴볼 것이다.
본론
1. 그래프
그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조로 정점과 간선들의 집합으로 구성되는데 G=(V, E)로 표시 한다. V(G)는 그래프G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 또한 정점의 차수는 그 정점에 부속된 간선들의 수이다. 그래프는 위상 순서, 최단 경로, 작업 네트워크 등에 이용된다.
2. 그래프 표현 방법
2.1 인접 행렬(Adjacency Matrix)
각 정점들 간의 연결을 행렬로 표현한 것이다. 인접 행렬 M은 n x n정방행렬로서 n은 그래프 내의 정점 수이다. 행렬의 (i, j)원소 Aij가 1이면 정점 Vi와 Vj가 인접해 있는 것이고, Aij가 0이면 정점 Vi와 Vj는 인접하지 않은 것이다.
[그림1] 그래프를 인접 행렬로 표현한 모습