DFS/BFS

 

#방문처리

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]

]

#그래프에 8개의 노드가 있으므로 처음 자리 0이므로 9개생성

visited = [False]*9

dfs(graph,1,visited)

#BFS : 너비 우선 탐색 => 가까운 노드부터 탐색하는 알고리즘

from collections import deque

def bfs(graph,start,visited):

    queue = deque([start])

    visited[start]=True

    #현재노드 방문처리

    while queue:

        v=queue.popleft()

        print(v,end=' ')

        for i in graph[v]:

            if not visited[i]:

                queue.append(i)

                visited[i]=True

graph = [

    [],

    [2,3,8],

    [1,7],

    [1,4,5],

    [3,5],

    [3,4],

    [7],

    [2,6,8],

    [1,7]

]

visited = [False]*9

bfs(graph,1,visited)

 

#reference : 이코테