그래프 - DFS

DFS(Depth First Search)

재귀를 사용한 깊이 우선 탐색

1. 시작 노드를 방문 처리
2. 재귀를 통해 인접한 다음 depth 노드를 방문 처리

#v는 노드 번호
def DFS(graph, v, visited):
	visited[v] = True
    print(v, end=" ")
    for elem in graph[v]:
    	if not visited[elem]:
        	DFS(graph, elem, visited)
            
#graph는 2차원 연결리스트
graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False]*9

DFS(graph, 1, visited)