그래프 - DFS 탐색 - 인접리스트 vs 인접행렬

그래프 탐색

 

그래프 + 시작점 주어진다.  => 둘다 모두 주어져야함.

시작점에서 간선을 타고 갈수있는 모든 점을 탐색하는것  

 

DFS  = 깊이우선탐색

Depth First Search 

특정 정점에서 시작하여 갈수있는 곳까지 계속 깊게깊게 들어간다음에 

더이상 갈 곳이 없으면 다시 돌아와서 또다른 길을 찾아가는것 

 

주로 재귀함수를 이용해서 구현 

다음 정점으로 가는걸.. 그위치에서 재귀호출하는 형태로 .. 

 

 

------

def dfs(vertex):   -> vertex 는 현재위치를 의미함 

현재위치에서 갈수있는 점들 보면서.. 더 갈수있으면.. 재귀함수 호출

 

 

연결된 점을 찾으면

그점으로 이동시키면됨

 

단, 이동의 의미는 

탐색을 새롭게 확장한다는 의미 

 

 

처음 만난거면 가는데 

이미 가본거면 또 갈 필요 없음

=> visited 배열을 활용한다. 

 

 

 

새로운 정점을 만났을때... 그 정점으로 가려면 

1. 연결되어있어야한다.( graph 행렬 등 ) 

and 

2. 방문한적 없어야한다.  (탐색하지 않은점, 처음 만난점) 

=> 이때 재귀호출을 해준다. 

 

 

DFS 의 기본코드 - 인접행렬의 경우 

def dfs(vertex):
	for curr_v in range(1,VERTICES_NUM +1): #해당 행을 탐색한다. 
    		if graph[vertex][curr_v] and not visited[curr_v]: #간선이 존재하고, 방문한적이 없는경우
        		visited[curr_v] = True # visited True 처리해주고  
            		dfs(curr_v) #재귀호출 해서 헤당 정점과 연결된 것들을 다시 탐색

 

꺼림칙한 부분 

 

맨처음에 

v 랑 연결된 모든 정점을 찾았음 

-> 뭐랑 연결되어있는지를 알아야... 방문했는지확인을 할것 

 

 

'어떤 점이랑 연결된 모든 정점 '

인접행렬 vs 인접리스트 중 ... 

인접리스트로 저장하는 것이 더 좋다! 

 

=> DFS 를 활용하고 싶다 => 인접리스트를 사용하는게 더 빠르다!! 

dfs 에서는 어떤 연산을 주로 던지게 되며, 

그 연산은 인접 행렬이 좋은지? 인접 리스트가 좋은지? 

 

DFS 의 기본코드 - 인접 리스트의 경우

불필요한 반복문을 돌 필요없이, 컴팩트하게 반복문을 돌수있다.

def dfs(vertex):
	for curr_v in graph[vertex]: #실제로 연결된애들만 확인한다.
            if not visited[curr_v]: #방문하지 않은점이라면 탐색시작 
                visited[curr_v] = True #방문체크하기 
                dfs(curr_v) # 재귀함수 호출로 재탐색

 

BFS  = 너비우선탐색

B First Search

 

는다음시간에