[그래프]DFS 구현 방법을 알아보자

1) 재귀를 이용한 DFS 구현 Pseudo code

 

G는 그래프, v는 정점(vertex)일 때,

DFS(G,v)
	lable v as discovered
	for all directed edges from v to w that are in G.adjacentEdges(v) do
		if vertex w is not labeled as discovered then
			recursively call DFS(G,w)

 

재귀를 이용한 DFS 구현 Python code

def recursive_dfs(v, discovered=[]):
	discovered.append(v)
    	for w in graph[v]:
    		if w not in discovered:
        		discovered = recusrive_dfs(w, discovered)
    	return discovered

 

 

2) 스택을 이용한 반복 구조로 DFS 구현 Pseudo code

DFS-iterative(G, v)
	let S be a stack
    	S.push(v)
    	While S is not empty do
    		v = S.pop()
        	if v is not labeled as discovered then
        		label v as discovered
            		for all edges from v to w in G.adjacentEdges(v) do
            			S.push(w)

 

 

스택을 이용한 반복 구조론 DFS 구현 Python code

def iterative_dfs(graph, start_v):
    visited = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)
    return visited