DFS & BFS

DFS와 BFS를 공부하기 앞서 큐와 스택에 대해서 간단하게 정리해봤다.

 

<Stack & Queue>

 

 

---

<DFS>

 

아래는 DFS에 관한 정리 및 구현 코드 이다.

 

 

재귀함수를 사용하는 것이 특징이다.

코드와 정리한 그림을 연결지어 생각하면 좋을듯 하다.

 

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False] * 9

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


dfs(graph, 1, visited)

 

---

<BFS>

 

아래는 BFS에 관한 정리 및 구현 코드 이다.

 

 

파이썬에서 Queue 사용시 deque를 import해서 사용하는 것이 좋다.

코드와 정리한 그림을 연결지어 생각하면 좋을듯 하다.

 

from collections import deque

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False] * 9

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


bfs(graph, 1, visited)