탐색 알고리즘 - DFS

DFS (Depth-First Search, 깊이 우선 탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

def dfs(graph, v, visited):
    visited[v] = True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

#각 노드가 연결된 정보를 2차원 리스트로 표현
graph=[
    [],#1번
    [2,3,8],
    [1,7,],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드의 방문이력을 저장할 1차원리스트
visited=[False]*9

dfs(graph,1,visited)

---

 

def dfs(graph, v, visited):
    visited[v] = True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

DFS를 함수로 만든 것.

매개변수로는

1.graph(각 노드가 연결된 정보를 2차원 리스트에 표현한 것),

2.v(현재 방문한 노드),

3.visited(각 노드의 방문 여부를 1차원 리스트에 표현한 것)

을 받는다.

 

현재 노드를 방문처리 하고, 현재 노드를 출력한 후,

연결된 노드 중 방문하지 않은 노드를 찾아간다.(재귀함수)