그래프의 깊이우선 탐색은 트리의 순회와 비슷하다.(그러나, 그만큼 우아하지는 않은것 같다.) 트리순회와 가장 큰 차이는 “방문여부”를 판별할 수 있는 방법이 제공되어야 하는것 뿐이다.
트리와 다르게 그래프는 여러 연결 경로가 있기 때문에 들어온곳을 다시 들어올수 있다.(-_- 이게 내가 그래프 탐색이 ‘우아’하지 않다고 생각하는 이유다) 예전에 방문했던곳을 탐색의 거점에서 제외하는게 그래프 탐색과 트리 순회의 핵심적인 차이이고, 그 때문에 “방문여부”를 알 필요가 있다.
방문여부는 Vertex가 방문여부를 알수 있도록 멤버로 가지고 있거나, Vertex의 ID를 인덱스로 가지는 배열이나 해쉬등을 이용해 방문여부를 표시함으로써 알수 있다. Vertex가 방문여부를 가지고 있다면, 방문전(혹은 후)에 Vertex의 방문여부를 초기화 해주어야 할 뿐만이 아니라, 하나의 그래프를 여러 Thread에서 탐색할 경우 Thread Safe하지 않으므로 그리 좋은 방법은 아니라고 생각한다.
그래프 탐색에는 깊이우선 탐색과 너비우선 탐색이 있는데 깊이우선 탐색이란, 연결된 Edge중 하나를 잡아 Vertex를 방문하고, 다시 그 Vertex에 연결된 Edge를 하나잡고 (마치, 아래로 타고 내려가듯이) 다음 Vertex를 방문하는 하다가, 더이상 연결된 Edge가 없으면 위로 올라가서 다음 Edge를 방문하는 방식(물론, 다음 Edge가 없으면 다시 위로 올라간다.)이다.
깊이우선 탐색은 다시, Vertex가 다음 방문을 위해 연결된 Edge가 없을때 위로 올라가는(예전 Vertex로 돌아가는) 방식에 따라 크게 스택을 사용하는 방식과 재귀를 사용하는 방식으로 나뉜다. - 물론 재귀를 사용하는 방식이 더 우아하다고 생각한다.
다음은 깊이우선 탐색 - 스택 버전을 Ruby로 구현한 경우다. (전체소스는 여기에 있다.) 살펴볼만한 부분이, 방문여부의 판별을 위해 루비의 Hash를 이용한 부분이다. 방문여부를 셀이 가지고 있지 않기 때문에 이 깊이우선 탐색은 Thread Safe하다.
def dfsWithStack( _rStartCell )
aCurrentCell = @aCellContainer[_rStartCell.cell_id]
return if aCurrentCell == nil
aMarkedCells = Hash.new
aDepthStack = Pok::Stack.new
#start dfs
aDepthStack.push_back( aCurrentCell )
print "DFS init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"
#stack loop
while aDepthStack.empty? == false
aCurrentCell = aDepthStack.pop_back
next if aMarkedCells[ aCurrentCell.cell_id ] == true
# marking
aMarkedCells[aCurrentCell.cell_id] = true
print "Cell id : " + aCurrentCell.cell_id.to_s + " is now visited\n"
#Test 확인을 쉽게 하기 위해 거꾸로 push 하도록 해서 pop할때는 작은수부터 나오게
aConnectedCells = aCurrentCell.edge_container.sort
aConnectedCells.reverse!
aConnectedCells.each do | id_value_array |
#연결된 셀을 선택
aCandidateCell = @aCellContainer[ id_value_array[0] ]
if aMarkedCells[aCandidateCell.cell_id] == nil
#셀이 예전에 탐색되지 않은 셀이라면, 스택에 넣어준다.
aDepthStack.push_back(aCandidateCell)
end
end
end
end
깊이우선 탐색 - 재귀버전은 방문여부를 알기위한 장치(역시, 여기서도 Hash를 사용했다)나 기타 초기화를 하는initial condition과 Base Case과 Recursive Case를 가지고 실제 재귀를 하는 Core 부분으로 나누었다.
def dfsRecursive( _rStartCell )
aCurrentCell = @aCellContainer[_rStartCell.cell_id]
return if aCurrentCell == nil
aMarkedCellsContainer = Hash.new
print "DFS(Recursive version) init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"
dfsRecursiveCore( aCurrentCell, aMarkedCellsContainer )
end
def dfsRecursiveCore( _rCell , _rMarkedCells)
_rMarkedCells[ _rCell.cell_id ] = true
print "Cell id : " + _rCell.cell_id.to_s + " is just now visited\n"
#테스트 확인을 쉽게 하기 위해 셀 번호순서대로 소팅하기
aConnectedCellsContainer = _rCell.edge_container.sort
aConnectedCellsContainer.each do | vertex_id_weight |
nCell_id = vertex_id_weight[0]
if _rMarkedCells[ nCell_id ] == nil
dfsRecursiveCore( @aCellContainer[nCell_id], _rMarkedCells )
end
end
end
| 깊이우선 탐색의 알고리듬 수행시간은 Adjacency List의 경우에 O( | v | + | E | )로 알려져 있으나 이게 뭔말인지는 모르겠고(-_-) Fundamentals of Data Structures in C 에서는 O(e)라고 소개하고 있는것과 내가 열심히 생각해본 결과(-_-)로 보아, Undirected Graph일 경우 Edge 갯수 * 2 번만큼 순회하므로 O(2E)이다. (…-_- 일것이다.) |