DFS & BFS

1. 그래프

-그래프는 자료구조의 일종으로 정점(Vertex)과 간선(Edge)로 이루어져있다.

   1.1 그래프의 표현

      -그래프는 크게 두가지 방법으로 저장한다.

      -인접행렬 (adjacency matrix) : 정점의 개수가 V개인 그래프에서 V x V 크기의 2차원 배열을 사용하여, A[i][j]=1 이         면 간선이 있다고 표시한다.

 

+ 방향이 있는 간선에서는 정점 1과 2가 연결되어있을때, A[1][2]와 A[2][1] 둘 중 하나에만 1을 대입 하지만, 방향이 없다면 A[1][2] = 1;  A[2][1] = 1; 으로 해줘야 한다.

++ 가중치가 있는 문제라면 1대신 가중치를 대입한다.

+++ 한 정점과 연결된 모든 간선을 찾는 시간은 O(V)로 표현된다.

      

      -인접 리스트(adjacency list) : 주로 vector를 사용하여 A[i]=i 와 연결된 정점을 포함한다.

 

+ 한 정점과 연결된 모든 간선을 찾는 시간은 O(차수)이다. ***차수 란 정점과 연결되어있는 간선의 개수를 의미.

 

2. 그래프의 탐색

크게 두가지 방식이 존재, DFS와 BFS이다. 목표는 임의의 정점에서 시작해서 연결되어있는 모든 정점을 한번씩 방문하는 것 이다.

 

   2-1. DFS (Depth First Search)

      -stack을 사용해서 구현한다.(더이상 갈 수 없는 정점이 나왔을때 이전 정점으로 돌아가야 하기때문)

      -소스코드(재귀 이용)

     

a는 인접행렬, check는 방문여부 기록 배열

   2-2. BFS

      -queue를 이용하여 구현한다.(큐의 맨 앞 원소에 연결되어있는 정점을 알아야 하기 때문)

      -소스코드(반복문 활용)

a와 check은 dfs와 같음

      **주의 할 점은 큐에 입력할때, check에도 방문했다고 기록해야함!

 

DFS 와 BFS는 코테에 굉장히 메인으로 나오는 알고리즘이라고 했으니 열공해야지...