그래프

#정의: 정점(Vertex)의 모음과 이 정점을 잇는 간선(Edge)의 모음간의 결합

#종류

- 무방향 그래프: (A,B) = (B,A)

- 방향성 그래프 : <A,B> =/ <B,A>

- 가중치 그래프(Weighted Graph), 네트워크 : 간선에 비용이나 가중치가 할당된 그래프

#표시예

V(G1) = {0,1,2,3} , E(G1) = {(0,1), (0,3), (1,2) }, E(G2) = {<0,1>, <1,2>}

 

 

 

 

그래프 탐색

#깊이우선탐색(Depth-Frist Search,DFS) : 더 나아갈 길이 보이지 않을때까지 깊이 들어가는 탐색

#DFS 탐색방법

1.시작 정점을 밟은 후 이 정점을 "방문했음" 으로 표시

2.인접정점중에 아직 방문하지 않은 곳을 선택하여 다시 깊이우선 탐색 시작

3.더 이상 인접정점이 없으면 이전정점으로 돌아와서 2번 수행

4.이전 정점으로 돌아가도 더 이상 방문할 이웃이 없으면 탐색 종료

#너비우선탐색(Breath Frist Search,BFS) : 꼼꼼하게 좌우를 살피면서 탐색하는 기법

#BFS 탐색방법

1. 시작 정점을 "방문했음"으로 표시하고 큐에 삽입(Enqueue)

2. 큐로부터 정점을 제거(Dequeue) 함. 제거한 정점이 이웃하고 있는 인접정점 중 아직 방문하지 않은 곳들을 "방문했음"으로 표시하고 큐에 삽입

3. 큐가 비게 되면 탐색 종료