DFS

DFS

• 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요함
• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게되면, 가장 마지막에 만났던 가림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입 선출 구조의 스택 사용

알고리즘

• 시작 정점 v를 결정하여 방문한다.

• 정범 v에 인접한 정점 중에서

  • 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다.

    그리고 w를 v로 하여 다시 두번째를 반복한다.

  • 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 두번째를 반복한다.

• 스택이 공백이 될 때까지 2)를 반복한다.

DFS 기본

input_str = "1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7"


lst = list(map(int,input_str.split(", ")))
grid = [[0]*8 for _ in range(8)]
# 1
from collections import defaultdict

# 그래프 만들기
graph = defaultdict(list)
for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]


    
    grid[a][b] = 1
    grid[b][a] = 1

    graph[a].append(b)
    graph[b].append(a)
    
from pprint import pprint

# pprint(grid)
# pprint(graph)


stack = []
visited = []
print(i)

stack.append(1)
visited.append(1)

while stack:

    tmp = stack[-1]


    for node in range(1,8): # 7 : node의 개수 1 ~ 7
        if grid[tmp][node] == 1 and node not in visited:
            stack.append(node)
            visited.append(node)
            break
    else:
        stack.pop()


    # for value in graph[tmp]:
    #     if value not in visited:
    #         stack.append(value)
    #         visited.append(value)
    #         break
    # else:
    #     stack.pop()
    
print(visited)

DFS 재귀

input_str = "1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7"


lst = list(map(int,input_str.split(", ")))



grid = [[0]*8 for _ in range(8)]
for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]    
    grid[a][b] = 1
    grid[b][a] = 1


from collections import defaultdict
graph = defaultdict(list)

for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]    
    graph[a].append(b)
    graph[b].append(a)
    
from pprint import pprint




stack = []
visited = []

stack.append(1)
visited.append(1)
cnt = 0
while stack:
    cnt += 1

    tmp = stack[-1]

    for node in graph[tmp]:
        if node not in visited:
            stack.append(node)
            visited.append(node)
            break
    else:
        stack.pop()
    
print(visited)
print(cnt)


visited = []

for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]    
    graph[a].append(b)
    graph[b].append(a)


def func(tmp):
    visited.append(tmp)
    for node in graph[tmp]:
        if node not in visited:
            # visited.append(node)
            func(node)

func(1)
print(visited)