[알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -3

* 참고: 코딩은 python기준으로 짰습니다.

 

저번글 ([알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -2 (tistory.com))에서는 1. 두 알고리즘을 사용하기 위한 준비와 2. DFS 코딩, 그리고 예시 문제를 살펴보았다. 이번에는 BFS 코딩 그리고 예시문제를 살펴보자.

 

 

<DFS(깊이 우선 탐색), BFS (너비 우선 탐색) 글 순서>

1.  DFS와 BFS의 간단한 개념 [알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -1 (tistory.com)

2. 두 알고리즘을 사용하기 위한 준비 [알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -2 (tistory.com)

3. DFS 코딩, 그리고 예시 문제 [알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -2 (tistory.com)

4. BFS코딩, 그리고 예시 문제 [이번글]

 

 

BFS (breadth first search)

• 큐 ("deque" 나 "queue" in python, "deque" 추천) vlfdy - 먼저 방문한 노드들의 자식들 (not 손주)들을 보기 때문 - 뒤에서 더 자세히 설명
• 특징: 각 노드마다 시작점으로 부터의 거리를(level, 층) 알 수 있음 ⇒ 각 정점과 시작점의 최단거리를 재야할 때 많이 사용 됨 ⇒ 최단거리문제다?! - BFS인가!?!
• 시간복잡도: O(V+E)
• 기본적으로 BFS만 할 때는 재귀 X (DFS는 재귀 필요) - 하지만, componenet를 샐 때에는 BFS재귀 사용

DFS에는 재귀가 들어가 있다. ([알고리즘] DFS(깊이 우선 탐색), BFS (너비 우선 탐색) -2 (tistory.com) - 컴포넌트 세는 문제)

BFS는 bfs정의에 bfs가 호출 되지 않음 (재귀 X)

• BFS코드

class graph:
    def __init__(self, n):
        self.N = n # node 개수
        self.adj = [[] for _ in range(n)]
        self.visited =[False]*n
        
    # 간선 추가
    def addedge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)
        
    # 간선 정렬 - 모든 리스트의 인접한 정점 번호 정렬
    def sortlist(self):
        for i in range(self.N):
            self.adj[i].sort()
            
    def bfs(self,now):
        self.visited[now] = True
        q = deque()
        # node 리스트에 첫번째 노드부터 
        q.append(now)
        while (q):
            noww = q.popleft()
            for next in self.adj[noww]:
                if not self.visited[next]:
                    self.visited[next] = True
                    q.append(next)

 

• Component (연결요소) 세는 문제

# 연결 요소의 수 - BFS
import sys
from collections import deque
sys.setrecursionlimit(10000)
sys.stdin = open("./input.txt", "r")
input = sys.stdin.readline

class graph:
    def __init__(self, n):
        self.N = n # node 개수
        self.adj = [[] for _ in range(n)]
        self.visited =[False]*n
        
    # 간선 추가
    def addedge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)
        
    # 간선 정렬 - 모든 리스트의 인접한 정점 번호 정렬
    def sortlist(self):
        for i in range(self.N):
            self.adj[i].sort()
            
    def bfs(self,now):
        self.visited[now] = True
        q = deque()
        # node 리스트에 첫번째 노드부터 
        q.append(now)
        while (q):
            noww = q.popleft()
            for next in self.adj[noww]:
                if not self.visited[next]:
                    self.visited[next] = True
                    q.append(next)
                    
    def numcomponent(self):
        count =0
        for i in range(self.N):
            if not self.visited[i]:
                count+=1
                self.bfs(i)
        return count

n, m = map(int,input().split()) 
g = graph(n)
for i in range(m):
    u,v = map(int, input().split()) 
    g.addedge(u-1,v-1)
print(g.numcomponent())

• 최단 거리 찾기 

def bfs():
    visited = [False] * N # 방문 여부를 저장하는 배열
    Q = deque()
    Q.append(0)
    visited[0] = True

    # 탐색 시작
    level = 0
    while Q:
        qSize = len(Q)
        print("------ level", level, "------")
        for i in range(qSize):
            curr = Q.popleft()
            print("node", curr, "visited")
            for next in adj[curr]:
                if not visited[next]:
                    visited[next] = True
                    Q.append(next)
        level += 1