[Python] DFS & BFS

그래프나 트리 구조에 대해서 충분한 설명이 있는 글은 아닙니다.
python 으로 DFS , BFS 를 구현하는 간단한 코드와 그에 대한 개념을 정리하고 있습니다.

 

그래프란?

- 사용

    지도, 네이게이션에 쓰임

    SNS, 메신저(팔로우/언팔로우)

    깃 VCS 에 쓰임

 

- 정점(vertext == node) 과 간선(edge)로 이루어져 있음.

 

- 구분

    1. 무방향 그래프(==양방향 그래프)

    2. 방향 그래프

    --------------------------------

    1. 순환 그래프

    2. 비순환 그래프

 

    방향성 비순환 그래프(DAG) Directed Acyclic Graph

 

- 연결요소

연결 요소 2개

 

트리란?

- 순환성X, 무방향

- 루트 노드, 리프 노드

- 노드 A에서 노드 B로 가는 경로는 반드시 존재하며 유일하다.

 

 

그래프를 어떻게 코드로?

1) 인접 행렬로 

	0	1	2	3
0	0	1	1	1
1	0	0	1	0
2	0	0	0	0
3	0	0	1	0

2) 인접 리스트로

0 | →1→2→3

1  | →2

2 |

3 | →2 

 

메모리: 인접행렬보다 인접리스트가 더 우수

시간: 인접 행렬이 인접리스트보다 더 우수 

 

 

그래프 탐색 알고리즘

1) DFS : 깊이 우선 탐색 

    스택 또는 재귀(재귀도 스택임) 사용해서 구현

    BackTracking (해를 찾기 위해서 체크 하다가, 제약 조건을 만족할 수 없다고 판단되면 즉시 뒤로 돌아가는(이 후보군을     체크 하지 않을 것을 표기 후/ 각 후보군들은 DFS로 확인한다.)

 

• 일반적인 DFS 시간 복잡도
  • 노드 수: V
  • 간선 수: E
    • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
  • 시간 복잡도: O(V + E)

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

 

2) BFS: 너비 우선 탐색

    큐 사용하여 구현

• 일반적인 BFS 시간 복잡도
  • 노드 수: V
  • 간선 수: E
    • 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
  • 시간 복잡도: O(V + E)

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited