[Algo] DFS이론

DFS(깊이우선탐색)

DFS는 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,가장 마지막에 만났던 갈림길 간성이 있느느 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 반복해 모든 정점을 방문하는 순회 방법이다.

V,E = map(int, input().split())

# 간선에 대한 인접 리스트 제작
G = [[]for _ in range(V+1)] # 인접리스트

for _ in range(E):
    u,v = map(int,input().split())
    G[u].append(v)
    G[v].append(u)

S = []                 # 스택(지나온 정점을 저장)
visited = [0] * (v+1)  # 방문정보 : 한번 갔던 곳은 또 가지 않겠다 why???
                       # 도르마무가 발생할 수 있으므로

# 1) 시작 정점 v를 결정하여 방문한다.
v = 1
visited[1] = 1
S.append(V)   # 현재 정점을 while전에 미리 넣어 둠

while S:   # 3) 스택이 공백이 될 때까지 2)를 반복
           # 2) 정점 V에 인접한 정점 중에서 ==> G[v]
           # 1방문하지 않은 정점 W가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다.
    for w in G[v]:
        if not visited[w]:
            # v === > w
            S.append(v)
            visited[w] = 1
            v = w # 그리고 w를 c로 하여 다시 2)를 반복한다.
            break
    else:
        v = S.pop()

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


# 재귀함수로 제작하기

def DFS(v):
    visited[v] = 1
    for w in G[v]:
        if not visited[w]:
            DFS(w)

DFS(1)