그래프 탐색

그래프 탐색 - BFS

그래프 탐색(순회)

그래프 순회는 비선형 구조인 그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것을 의미한다.

두가지 방법

AdjMatrixTest.java

• 너비 우선 탐색(Breadth First Search, BFS)
• 깊이 우선 탐색(Depth First Search, DFS)

BFS(Breadth First Search)

너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함

BFS 알고리즘

입력 파라미터 : 그래프 G와 탐색 시작 정점

BFS(G, v) // 그래프 G, 탐색 시작 정점 v
  큐 생성
  시작 정점 v를 큐에 삽입
  정점 v를 방문한 것으로 표시
  while(큐가 비어 있지 않은 경우) {
    t <- 큐의 첫번재 원소 반환
    for(t와 연결된 모든 간선에 대해){
      u <- t의 인접 정점
      u가 방문되지 않은 곳이면,
      u를 큐에 넣고, 방문한 것으로 표시
    }
  }
end BFS()

그래프 탐색 - DFS

DFS 알고리즘

재귀

G : 그래프
DFS(v) // v: 탐색 정점
  visited[v] <- true // v 방문 설정
  For each all w in adjacency(G, v) // 인접 정점
    If visited[w] != True // 방문하지 않았다면
      DFS(w)