DFS,BFS, 다익스트라, 플로이드 와샬

 

그래프 탐색의 목적은 모든 정점을 한 번씩 방문 하는 것이다. 어떻게 방문할 것이냐에 따라 DFS와 BFS로 나뉜다.

 

DFS - 깊이 우선 탐색

 

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

 

• 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식.
• 모든 노드를 방문하고자 하는 경우에 이 방법을 사용
• 그래프의 구조를 파악하는데 유용
• BFS에 비해 간단하지만 검색 속도가 느림
• 스택 또는 재귀함수로 구현
• 활용: 미로 찾기

 

DFS 구현 방법
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

n,m,v = map(int,sys.stdin.readline().split())

# 그래프 생성  
graph = [[0] * (n+1) for _ in range(n+1)]

# 인접 행렬로 무방향 그래프
for i in range(m):
    n1, n2 = map(int,sys.stdin.readline().split())
    graph[n1][n2] = 1 
    graph[n2][n1] = 1

#방문 체크할 리스트
visited_dfs = [False] * (n+1)

def dfs(v):
    visited_dfs[v] = True
    print(v, end =" ")
    
    for i in range(1,n+1):
        if graph[v][i]==1 and not visited_dfs[i]:
            dfs(i)

dfs(v)

 

BFS - 너비 우선 탐색

 

• 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
• 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 주로 최단 경로를 찾고 싶을 때 사용
• 큐를 이용하여 구현
• 활용: 최단 경로 찾기, 노드 간 최단거리 구하기 등

 

BFS 구현 방법
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

n,m,v = map(int,sys.stdin.readline().split())

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

# 인접 행렬
for i in range(m):
    n1, n2 = map(int,sys.stdin.readline().split())
    graph[n1][n2] = 1 
    graph[n2][n1] = 1

visited_bfs = [False] * (n+1)

def bfs(v):
	#큐에 생성, 큐에 시작 노드 삽입
    q = deque()
    q.append(v)
    
    #방문 처리
    visited_bfs[v] = True
    
    while q:
    	#큐에서 노드를 꺼내 x에 저장
        x = q.popleft()
        
        for i in range(1,n+1):
        	if graph[x][i] == 1 and not visited_vfs[i]:
            	#큐에 삽입하고 방문 처리
            	q.append(i)
                visited_bfs[i] = True
             
bfs(v)

 

- DFS와 BFS의 시간복잡도

DFS - 인접리스트 : O(V+E) 인접행렬 : O(V^2) 공간복잡도 O(V)
BFS - 인접리스트 : O(V+E) 인접행렬 : O(V^2) 공간복잡도 O(V)

---

 

 

1. 그래프의 모든 정점을 방문하는 문제
   -> 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS,BFS 둘 어느 것을 사용해도 무관

 

2. 경로의 특징을 저장해야 하는 문제(a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다 등)
   -> DFS 사용. (BFS는 경로의 특징을 가지지 못 함)

 

3. DFS는 임의의 정점을 발견할 때마다 직전 원소 속성을 u로 지정해서 이 사건을 기록한다.

 

4. 최단 거리 구하는 문제

   ->미로 찾기 등 최단거리를 구해야 할 경우 BFS 유리

 

5. 검색 대상 그래프가 정말 크다면 DFS

 

6. 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

 

다익스트라

• 대표적인 최단 경로 탐색 알고리즘
• 특정한 하나의 노드에서 다른 모든 노드로 가는 최단 경로를 알려준다.
• 가장 적은 비용을 하나씩 선택을 해서 그 적은 비용을 가지는 노드의 인접한 노드들로 가는 비용을 하나씩 계산하는 방식
• 음의 간선은 포함x -> 현실 세계에 사용하기 매우 적합한 알고리즘
• 동적 계획법(다이나믹 프로그래밍)인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문'
  (동적 계획법 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법)
• 인접 행렬 사용하면 시간복잡도 O(n^2) , 우선순위 큐 사용하면 O(ElogV)

 

플로이드 와샬

• 모든 노드에서 모든 노드로의 최단 경로 탐색 알고리즘
• 거쳐가는 노드를 기준으로 알고리즘을 수행
• 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드 간 최소의 비용을 계산
• 인접 행렬 사용, 시간 복잡도 O(N^3)

 

출처
DFS/BFS https://devuna.tistory.com/32 , 선애님 정리본..
다익스트라 https://m.blog.naver.com/ndb796/221234424646
플로이드 와샬 https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm