DFS

1. dfs 함수

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end='')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

현재 노드의 visited를 True로 해주고 출력한다

현재 노드의 연결 노드들 중 방문하지 않은 노드에서 dfs를 호출한다

 

v=1일 경우,

visited[1] = True

graph=[
    [], #
    [2, 3, 8], # 1 node와 연결된 노드들 # 2 노드를 방문하지 않았으므로 dfs(graph, 2, visited) (만약 방문했다면 다음 연결 노드인 3으로 넘어감)
    [1, 7], # 2 node와 연결된 노드들
    [1, 4, 5], # 3 node
    [3, 5], # 4 node
    [3, 4], # 5 node
    [7], # 6 node
    [2, 6, 8], #7 node
    [1, 7] # 8 node
]

 

2. graph 리스트 만들기

graph=[
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

노드의 편의성을 위해 첫번째는 [ ]로 해준다

1번노드 [2,3,8] 연결, 2번 노드 [1,7] 연결 ...

그림으로 나타낸 graph 모습

dfs 탐색을 하면 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

3. visited

visited=[False] * 9

노드 개수 만큼 visited 리스트를 만들어준다

 

4. dfs 탐색

dfs(graph, 1, visited) #12768345

1. dfs(graph, 1, visited)

def dfs(graph, v, visited):
    visited[v] = True # visited[1]을 True로 만든다 -> visited[0,1,0,0,0,0,0,0,0]
    print(v, end='') # 1 출력

    for i in graph[v]: # grahp[1]인 [2,3,8] 에서
        if not visited[i]: 
            dfs(graph, i, visited) # visited[2] (3,8) 는 False -> dfs(graph,2,visited) (dfs(graph,3,visited), dfs(graph,8,visited))

 

2. dfs(graph, 2, visited)

def dfs(graph, v, visited):
    visited[v] = True # visited[1]을 True로 만든다 -> visited[0,1,1,0,0,0,0,0,0]
    print(v, end='') # 2 출력

    for i in graph[v]: # grahp[2]인 [1,7] 에서
        if not visited[i]: 
            dfs(graph, i, visited) # visited[1] 는 True,

                                                visited[7]은 False -> dfs(graph,7,visited)

 

3. dfs(graph, 7, visited)

def dfs(graph, v, visited):
    visited[v] = True # visited[7]을 True로 만든다 -> visited[0,1,1,0,0,0,0,1,0]
    print(v, end='') # 2 출력

    for i in graph[v]: # grahp[7]인 [2,6,8] 에서
        if not visited[i]: 
            dfs(graph, i, visited) # visited[2] 는 True,

                                                visited[6] (8)은 False -> dfs(graph,6,visited) (dfs(graph,8,visited))

 

4. dfs(graph,6,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)

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)