너비 우선 탐색(BFS) 알고리즘

7085 단어 codenewbiealgorithmscomputersciencebeginners
안녕하세요 여러분, 이 아름다운 날에 너비 우선 검색에 대해 이야기하겠습니다.

BFS(Breadth-First Search Algorithm)의 정의



너비 우선 탐색(Breadth-First Search): 재귀와 데이터 구조를 사용하여 트리와 그래프를 탐색하고 탐색하는 알고리즘으로 이 알고리즘은 노드를 두 번 이상 처리하지 않도록 합니다.

BFS의 시간 복잡도와 공간 복잡도




공간 복잡성
오(V)


시간 복잡도
오(V+E)


너비 우선 검색 애플리케이션


  • 구글 지도
  • 체니의 알고리즘
  • 검색 엔진
  • 피어 투 피어 네트워킹
  • 포드-풀커슨 알고리즘

    • 너비 우선 검색 접근 방식


  • 대기열 초기화
  • 목록에 노드를 삽입하여 노드를 방문한 것으로 표시합니다
    • .
  • 정점을 대기열에 삽입하십시오

  • len(queue) > 0일 때:
  • 대기열의 첫 번째 항목 삭제
  • 방문으로 표시하고 삭제된 항목의 인접한 모든 방문하지 않은 노드를 푸시합니다.


    • 파이썬에서 너비 우선 검색 구현



    more details...

    파이썬에 익숙하지 않다면 이것을 확인하는 것이 좋습니다

    # CODE FROM https://favtutor.com/blogs/breadth-first-search-python

graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visitedNodes = [] 
queue = []   

def bfs(visitedList: list, graph: dict, node):
    visitedList.append(node)
    queue.append(node)

    while queue:        
        m = queue.pop(0) 
        print (m, end = "\t") 
        for adjacent in graph[m]:
            if adjacent not in visitedList:
                visitedList.append(adjacent)
                queue.append(adjacent)

bfs(visitedNodes, graph, '5') # 5 3 7 2 4 8


    참조 및 유용한 리소스


  • https://www.javatpoint.com/breadth-first-search-algorithm#:~:text=Breadth%20first%20search%20is%20a,until%20it%20finds%20the%20goal.
  • https://www.pythonpool.com/bfs-python/#:~:text=Breadth%2Dfirst%20search%20(BFS)%20in%20python%20is%20an%20algorithm,dictionaries%20and%20lists%20in%20python.
  • https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/#:~:text=The%20Time%20complexity%20of%20BFS,and%20E%20stands%20for%20edges.
  • https://stackoverflow.com/questions/9844193/what-is-the-time-and-space-complexity-of-a-breadth-first-and-depth-first-tree-tr
  • https://medium.com/edureka/breadth-first-search-algorithm-17d2c72f0eaa
  • https://www.programiz.com/dsa/graph-bfs
  • https://www.quora.com/What-are-some-real-life-examples-of-Breadth-and-Depth-First-Search
  • https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/
  • https://www.javatpoint.com/breadth-first-search-algorithm
  • https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm

    • 좋은 하루 되세요!!
    파이썬 가상 환경
    반복문

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage