BFS,DFS에 대해서

간선의 가중치가 없는 그래프 탐색!

---

 

 

BFS-너비탐색 최단거리를 구하는 문제에서 자주 사용 큐를 이용하여 구현

탐색할수록 메모리 업업

최단거리는 무조건 보장

 

def bfs(graph, start_node):# 너비 # 큐사용해서 한쪽으로는 하나씩 꺼내주고 다른쪽으로는 꺼낸값의 자식노드를 입력받는 형태로 구성 
    visit = list()
    queue = list()

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])

    return visit

BFS를 사용하는 경우, 알고리즘 문제풀이

그래프 탐색(BFS, DFS)에 대한 알고리즘 문제풀이

---

 

 

DFS -깊이 이동한 정점의 값을 가지고 계속 연산을 하는 경우(재귀적으로 호출되는경우)

       -->경로가 필요하다면(숫자 만들기, 경우고르기 등등을 그래프로 만들어 경로로 생각 해야함)

       -->스택이나 재귀함수(인접행렬)로 구현!

 

def dfs(graph, start_node):#깊이 스택사용 가장깊은곳이 아닌 왼쪽끝으로 먼저 탐색 하면서 밑으로 탐색 먼말인지 이해됨?
    visit = list()
    stack = list()

    stack.append(start_node)

    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(reversed(graph[node]))# 거꾸로넣기
         
    return visit

 

 

 

틀린점이 있다면 댓 달아주세요!