그래프(DFS, BFS)

 

그래프를 구현하기 위해 필요한 요소

• 노드
• 간선(노드간 연결 유무)
• 가중치(노드간 간선에 대한 가중치)
• 방향(노드간 연결 됐을때 방향이 있는 경우)

그래프 구현 방법

• 인접 행렬
  • 가중치가 있는 경우, 가중치에 대해 초기화 할때는 inf(무한대의 값) 혹은 -1로 초기화 

 

보통 인접 행렬로 구현많이 함.

 

 

깊이 우선 탐색

 

시작 노드부터 탐색을 시작해, 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문함

최대 깊이 노드까지 방문한 다음, 이전에 방문한 노드로 거슬러 올라가면서 해당 노드와 연결된 노드 중 방문하지 않은 노드로 

다시 최대 깊이 까지 차례대로 방문합니다. 

 

절차

1. 스택이 비었는지 확인한다. 스택이 비었다는 건 방문할 수 있는 모든 노드를 방문했음을 의미한다. 따라서 스택이 비었으면 탐색을 종료한다. 
2. 스택에서 노드를 팝한다. 팝한 원소는 최근에 스택에 푸시한 노드다. 
3. 팝한 노드의 방문 여부를 확인한다. 아직 방문하지 않았으면, 노드를 방문 처리한다. 
4. 방문한 노드와 인접한 모든 노드를 확인한다. 그리고 그 중에서 아직 방문하지 않은 노드를 스택에 푸시한다. 스택은 FILO 구조이므로, 방문 순서를 오름차순으로 고려한다면 역순으로 노드를 푸시해야한다. 

 

너비 우선 탐색 

 

시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘이다. 

여기서 말하는 거리는 시작 노드와 목표 노드까지의 차수이다.