playdataAlgo DFS, BFS

DFS

---

DFS - 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.

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

---

[step0]- 그래프 준비(1부터 시작, 가장 낮은 노드번호에 우선순위 부여)

---

[step1]- 시작 노드인 '1'을 스택에 삽입하고 방문 처리를 해준다.

---

[step2]-스택의 최상단 노드인 '1'에 방문하지 않은 노드 '2', '3', '8' 이 있다.

• 이 중에서 가장 작은 노드인 '2'를 스택에 넣고 방문 처리를 해준다.

---

[step3]-스택의 최상단 노드인 '2'에 방문하지 않은 노드 7번을 스택에 넣고 방문 처리를 해준다.

---

[step04]-스택의 최상단 노드인 '7'에 방문하지 않은 노드 '6'과 '8'중 낮은수인 6번 노드를 넣어준다.

---

[step05]-6번에 방문하지 않은 노드가 없기때문데 스택에서 '6'을 꺼내준다

---

---

[step06] '7'번이 방문하지 않은 노드 8번을 스택에 넣어준다

✨이 과정을 반복하면 탐색순서는: 1->2->7->6->8->3->4->5

#//각 노드강 연결된 정보를 표현(2차원 리스트)
graph = [
        [],
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1,7],
]

#//각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9

#//DFS메서드 정의
def dfs(graph, v, visited):
    #// 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = " ")
    #// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    #// 방문하지 않은 노드를 만났을때 다시 재귀함수 실행
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
#//정의된 DFS함수 호출
dfs(graph, 1, visited)

---

BFS(Breadth-First Search)

BFS - 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.

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

[step0] - 그래프 준비(방문기준: 번호가 낮은 인접 노드부터)-시작 노드 1

---

[step1] - 시작 노드인 '1'을 큐에 삽입하고 방문 처리

---

[step2] - 큐에서 노드'1'을 꺼내 방문하지 않은 인저버 노드 '2', '3', '8'을 큐에 삽입하고 방문 처리

---

[step3] - 큐에서 노드 '2'를 꺼내 방문하지 않은 인접 노드 '7' 을 큐에 삽입하고 방문 처리

---

[step4] - 큐에서 노드'3'을 꺼내 방문하지 않은 인접 노드 '4', '5', 를 큐에 삽입하고 방문 처리

[step5] - 큐에서 노드'8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시

[step6] - 이러한 과정을 반복

전체 노드의 탐색순서 : ✨1->2->7->6->8->3->4->5

#//
from collections import deque

graph = [
        [],
        [2, 3, 8],
        [1, 7],
        [1, 4, 5],
        [3, 5],
        [3, 4],
        [7],
        [2, 6, 8],
        [1,7],
]

visit = [False]*9
# BFS메서드 정의
def bfs(graph, start, visit):
    #// 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    #//현재 노드를 방문 처리
    visit[start] = True

    #//큐가 빌때까지
    while queue:
        #//큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end = " ")
        #// 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True

bfs(graph, 1, visit)