Graph Traversal 방법은 항상 저를 매료 시켰습니다. 효과적인 P2P 통신 수행부터 GPS를 사용하여 가장 가까운 레스토랑 및 카페 찾기에 이르기까지 순회 방법은 실제 시나리오에서 다양한 애플리케이션 세트를 가지고 있습니다. Breadth-First Search 알고리즘에 대한이 블로그에서는 그래프 탐색 방법의 논리에 대해 논의하고 예제를 사용하여 Breadth-First Search 알고리즘의 작동을 이해합니다.
인공 지능 및 기계 학습에 대한 심층적 인 지식을 얻으려면 라이브에 등록 할 수 있습니다. 24/7 지원 및 평생 액세스를 제공하는 Edureka
다음은 주제 목록입니다. 이 블로그에서 다루는 내용 :
그래프 순회 소개
처리를 위해 그래프를 방문하고 탐색하는 프로세스를 그래프 순회라고합니다. 더 구체적으로 말하자면 모든 정점을 정확히 한 번 탐색하도록 그래프의 각 정점과 가장자리를 방문하고 탐색하는 것입니다.
간단하게 들립니다! 하지만 문제가 있습니다.
Breadth-First Search, Depth First Search 등과 같은 몇 가지 그래프 순회 기술이 있습니다. 문제는 그래프를 사용하는 것입니다. 특정 문제를 해결하는 데 가장 적합한 순회 기법. 이를 통해 Breadth-First Search 기법을 소개합니다.
폭 우선 검색 알고리즘이란 무엇입니까?
Breadth-First Search 알고리즘은 임의의 초기 노드 (소스 또는 루트 노드)를 선택하고 모든 노드와 해당 하위 노드를 방문하고 탐색하는 방식으로 그래프 계층별로 탐색을 시작하는 그래프 탐색 기술입니다.
더 나아가 예제를 통해 Breadth-First Search를 이해하기 전에 그래프 순회와 관련된 두 가지 중요한 용어에 대해 알아 보겠습니다.
이를 더 잘 이해하려면 위의 그림을 참조하십시오.
예제를 통한 폭 우선 검색 알고리즘 이해
폭 우선 검색 알고리즘은 문제를 해결하기 위해 간단한 수준 기반 접근 방식을 따릅니다. 아래의 이진 트리 (그래프)를 고려하십시오. 우리의 목표는 Breadth-First Search Algorithm을 사용하여 그래프를 탐색하는 것입니다.
시작하기 전에 Breadth-First Search 알고리즘과 관련된 주요 데이터 구조에 대해 잘 알고 있어야합니다.
셀레늄의 데이터 기반 테스트
큐는 First-In-First-Out 방법론을 따르는 추상 데이터 구조입니다 (먼저 삽입 된 데이터가 먼저 액세스 됨). 양쪽 끝이 열려 있으며 한쪽 끝은 항상 데이터를 삽입 (대기열에 넣음)하는 데 사용되고 다른 쪽 끝은 데이터를 제거하는 데 사용됩니다 (대기열 제거).
이제 Breadth-First Search를 사용하여 그래프를 순회하는 것과 관련된 단계를 살펴 보겠습니다.
1 단계: 빈 대기열을 가져옵니다.
2 단계: 시작 노드 (노드 방문)를 선택하고 대기열에 삽입합니다.
3 단계 : 대기열이 비어 있지 않은 경우 대기열에서 노드를 추출하고 해당 하위 노드 (노드 탐색)를 대기열에 삽입합니다.
4 단계 : 추출 된 노드를 인쇄하십시오.
혼란스러워도 걱정하지 마세요. 예를 들어 이해하겠습니다.
아래 그래프를 살펴보면 Breadth-First Search 알고리즘을 사용하여 그래프를 탐색합니다.
추상 클래스와 인터페이스의 차이점
이 경우 'a'노드를 루트 노드로 할당하고 아래쪽으로 이동하기 시작하고 위에서 언급 한 단계를 따릅니다.
위 이미지는 Breadth-First Search Algorithm의 종단 간 프로세스를 보여줍니다. 좀 더 자세히 설명하겠습니다.
- 'a'를 루트 노드로 할당하고 큐에 삽입합니다.
- 대기열에서 노드‘a’를 추출하고‘a’의 하위 노드 즉,‘b’와‘c’를 삽입합니다.
- 프린트 노드 'a'.
- 대기열이 비어 있지 않고 노드‘b’및‘c’가 있습니다. ‘b’는 대기열의 첫 번째 노드이므로 추출하여‘b’의 하위 노드, 즉 노드‘d’와‘e’를 삽입 해 보겠습니다.
- 대기열이 비워 질 때까지이 단계를 반복합니다. 이미 방문한 노드는 대기열에 추가해서는 안됩니다. 다시.
이제 Breadth-First Search 알고리즘의 의사 코드를 살펴 보겠습니다.
폭 우선 검색 알고리즘 의사 코드
다음은 Breadth-First Search 알고리즘을 구현하는 의사 코드입니다.
입력 : s를 소스 노드 BFS (G, s)로 Q를 대기열로 둡니다. Q.enqueue (s)는 s를 방문한 것으로 표시하고 (Q는 비어 있지 않음) v = Q.dequeue () w가 방문하지 않은 경우 그래프 G에서 v의 모든 이웃에 대해 w를 방문한 것으로 표시합니다. Q.enqueue (w) w를 방문한 것으로 표시
위의 코드에서 다음 단계가 실행됩니다.
- (G, s) 입력, 여기서 G는 그래프, s는 루트 노드
- 대기열‘Q’가 생성되고 소스 노드‘s’로 초기화됩니다.
- ‘s’의 모든 하위 노드가 표시됩니다.
- 대기열에서‘s’를 추출하고 하위 노드를 방문합니다.
- v의 모든 자식 노드 처리
- 하위 노드를 추가로 방문하기 위해 Q에 w (하위 노드)를 저장합니다.
- 'Q'가 될 때까지 계속 빈
블로그를 마무리하기 전에 Breadth-First Search 알고리즘의 몇 가지 응용 프로그램을 살펴 보겠습니다.
폭 우선 검색 알고리즘의 응용
Breadth-first Search는 놀라운 범위의 응용 프로그램이있는 간단한 그래프 탐색 방법입니다. 다음은 Bread-First Search가 사용되는 몇 가지 흥미로운 방법입니다.
검색 엔진의 크롤러 : Breadth-First Search는 웹 페이지 색인 생성에 사용되는 주요 알고리즘 중 하나입니다. 알고리즘은 소스 페이지에서 순회를 시작하고 페이지와 관련된 모든 링크를 따릅니다. 여기서 각 웹 페이지는 그래프의 노드로 간주됩니다.
GPS 내비게이션 시스템 : Breadth-First Search는 GPS 시스템을 사용하여 주변 위치를 찾는 데 사용되는 최고의 알고리즘 중 하나입니다.
가중치가 적용되지 않은 그래프에 대한 최단 경로 및 최소 스패닝 트리 찾기 : 가중치가없는 그래프의 경우 최단 경로의 기본 개념은 가장자리 수가 가장 적은 경로를 선택하는 것이기 때문에 최단 경로를 계산하는 것은 매우 간단합니다. Breadth-First Search는 소스 노드에서 시작하는 최소 노드 수를 순회하여이를 허용 할 수 있습니다. 마찬가지로 스패닝 트리의 경우 Breadth-First Search 또는 Depth-first traversal 방법 중 하나를 사용하여 스패닝 트리를 찾을 수 있습니다.
방송: 네트워킹은 통신을위한 패킷으로 우리가 부르는 것을 사용합니다. 이러한 패킷은 탐색 방법을 따라 다양한 네트워킹 노드에 도달합니다. 가장 일반적으로 사용되는 순회 방법 중 하나는 Breadth-First Search입니다. 네트워크의 모든 노드에서 브로드 캐스트 된 패킷을 전달하는 데 사용되는 알고리즘으로 사용됩니다.
피어 투 피어 네트워킹 : Breadth-First Search는 피어 투 피어 네트워크에서 모든 인접 노드를 찾는 순회 방법으로 사용할 수 있습니다. 예를 들어 BitTorrent는 P2P 통신을 위해 Breadth-First Search를 사용합니다.
이것이 Breadth-First Search 알고리즘의 작동에 관한 것입니다. 이제 그래프를 횡단하는 방법을 알았으니 더 자세히 알고 싶으 실 것입니다. 다음은 관심을 끌 수있는 몇 가지 관련 블로그입니다.
이것으로 우리는이 블로그의 끝으로 왔습니다. 이 주제와 관련하여 질문이 있으시면 아래에 의견을 남겨 주시면 연락 드리겠습니다.
자바에 숨어있는 메소드는 무엇입니까
인공 지능 및 기계 학습에 대한 전체 과정에 등록하려는 경우 Edureka는 특별히 선별 된 지도 학습, 비지도 학습 및 자연어 처리와 같은 기술에 능숙하게 만들 것입니다. 여기에는 딥 러닝, 그래픽 모델 및 강화 학습과 같은 인공 지능 및 기계 학습의 최신 발전 및 기술적 접근에 대한 교육이 포함됩니다.