[파이썬] DFS와 BFS 3 - 코드 뜯어보기

 전 시간에는 트리와 그래프를 순회하여 알고리즘이 어떻게 작동하는지 알아보았습니다.

 이번엔 직접 코드로 옮겨봅시다.

 

BFS 소스코드

def BFS(start): 
    visit = []
    queue = []
    queue.append(start)
    visit.append(start)
    while queue:
        now_node = queue.pop(0)
        print(now_node, end='')
        for i in range(7):
            if matrix[node][i] == 1 and not i in visit:
                queue.append(i)
                visit.append(i)

 BFS 방식으로 그래프를 순회하는 소스코드입니다. matrix는 1차시에서 만들어둔 그래프를 사용하시면 되겠습니다.

 먼저, 매개변수로 시작 정점을 입력받습니다. 시작 노드는 늘 1번이므로 BFS(1)로 시작합니다.

 함수의 시작에서는 배열을 두 개 만들어줍니다. 하나는 행선지를 저장할 큐이며, 하나는 방문한 노드를 확인할 리스트입니다. 그리고 시작 정점을 큐에 넣고, 방문한 노드로 표시해줍니다.

 그리고 큐에 있는 행선지를 하나씩 꺼내며 now_node에 저장합니다. 현재 있는 노드를 출력한 뒤, 다른 노드들과의 연결 관계를 확인합니다.

 만약 i번째 노드와 연결되어있고, 방문하지 않았다면 큐에 넣고 방문한 노드로 표시합니다.

 

DFS 소스코드

def DFS1(start, visit):
    print(start, end='')
    visit.append(start)
    for i in range(7):
        if matrix[start][i] == 1 and not i in visit:
            DFS1(i, visit)
    return

 DFS 방식으로 그래프를 순회하는 소스코드입니다.

 아까는 시작 정점만 받았지만 이번에는 재귀 함수로 구현해야 하므로 방문한 노드도 매개변수로 입력받습니다. 시작 정점은 1번, 아무것도 방문하지 않았으니 리스트를 하나 입력해줍니다. DFS(1, [])이 되겠네요.

 시작 정점을 출력하고, 방문한 노드에 추가합니다. 연결 상태를 확인한 뒤, i번째 노드와 연결되어있고 방문하지 않았다면 해당 노드에서 DFS를 다시 시작합니다. 1번 노드는 2번과 연결되어있으니 DFS(2, [1])이 되겠네요.

 해당 노드에서 방문할 수 있는 모든 노드를 방문했다면 return으로 되돌아와 1번 노드에서부터 다시 탐색합니다.

 

 이상으로 BFS와 DFS를 다뤄보았습니다. 이해가 안되신다면 소스코드를 직접 디버깅해보는 방법을 추천드립니다. 댓글 남겨주셔도 괜찮고, 본격적인 문제풀이는 문제풀이에서 다루도록 하겠습니다.