[알고리즘] BFS DFS 코드 정리

● BFS DFS 란?

bfs dfs 둘다 그래프를 탐색하는 방법으로 bfs는 너비우선 탐색, dfs는 깊이우선 탐색이라 불린다.

 

보통 코딩테스트에서 bfs가 많이 사용 bfs 안되면 dfs 고려

 

 

● BFS, DFS 입력 그래프 표현 방식

시작 노드로 부터 가까운 노드부터 탐색, 방문 여부를 반드시 검색해야함

그래프 입력은 인접행렬 방식으로

[ [], [2,3,8], [1,7], ... ]  -> 0번노드 x  /  1번노드 2,3,8번 노드와 연결  / ...

 

인접리스트 방식으로 주어진다면

[ [1,2], [1,3], [1,5], [5,2], ... ]  ->  1번노드 2, 3, 8번 노드와 연결 / ...

 

인접리스트 -> 인접행렬

#n = node개수, l = 연결된 노드 쌍의 개수

net = [[]*(n+1) for _ in range(n+1)]

for i in range(l):
    a, b = map(int,input().split())
    net[a].append(b)
    net[b].append(a)

 

 

 

● BFS 구현

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

3. 2번과정을 반복

visited = [False]*9

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v)
        
        for i in graph(v):
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

 

 

 

● DFS 구현

 

1. 탐색 시작 노드를 스캑에 삽입하고 방문처리를 한다.

2.스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다.

3.방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.

4. 2,3을 반복한다.

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