[TIL_알고리즘] 완전 탐색 DFS(Depth First Search)

완전 탐색

 

깊이우선방식으로 모든 정점을 방문하여 (전수조사)

 

BFS, DFS : 비선형 구조인 그래프에서 모든 데이터를 완전 검색하는 방법

- 시작 정점에서 한 방향으로 가능한 정점까지 탐색해 나가다가 그 이후에 바로 이전 정점으로 되돌아와서 방문하지 않은 다른 방향의 정점으로 탐색을 계속 반복해 나감. 

- 바로 이전의 정점으로 되돌아가서 DFS를 반복하는 방법이므로 LIFO의 스택 사용

 

here=현위치 next=다음위치

다음위치를 못찾으면 stack에서 엄마를 찾아 방문하지 않은 엄마정점의 다음 위치 찾기

stack 엄마

visted 방문여부

스택이 완전 비워있다면 끝

 

[스택 사용]

print(here)

visted[here] = True

while here:

  next = findnext(here)

  if next : push(here)

  while next:

    here = next

    print(here)

    visted[here] = True

    next = findnext(here)

    if next : push(here)

  here = pop()

 

[파이썬으로 구현]

apppen(), pop() 사용

 

here=현위치 next=다음위치

다음위치를 못찾으면 stack에서 엄마를 찾아 방문하지 않은 엄마정점의 다음 위치 찾기

stack 차수 넣기

visted 방문 정점 적기

스택이 완전 비워있다면 끝

 

# node edge

# 7 8

# here next

# 1 2
# 1 3
# 1 4
# 1 5
# 2 6
# 2 7
# 5 6
# 6 7

 

def dfs(start):

  visited=[]

  stack=[start]

  while stack:

    here=stack.pop()

    if here not in visited:

      visited.append(here)

      stack.extend(sorted(MyMap[here],reverse=True))

  return visited

 

NodeNum, EdgeNum = map(int,input().split())

print(NodeNum)

MyMap= [[] for i in range(NodeNum+1)]

for i in range(EdgeNum):

  start, stop  = map(int,input().split())

  MyMap[start].append(stop)

  MyMap[stop].append(start)

 

print(dfs(1)) #[1, 2, 6, 5, 7, 3, 4]