1. Uczyć się
    2. /
  2. Courses
    3. /
  3. Python으로 시작하는 네트워크 분석
Connected

Exercise

최단 경로 I

이웃 노드를 찾는 방법을 활용해 네트워크에서 경로를 찾아볼 수 있어요. 두 노드 사이의 경로를 찾는 한 가지 알고리즘은 "너비 우선 탐색"(BFS) 알고리즘입니다. BFS에서는 특정 노드에서 시작해 그 노드의 이웃, 그리고 이웃의 이웃을 차례로 탐색하면서 목적지 노드를 찾을 때까지 진행해요.

경로 탐색 알고리즘은 노드의 중요도를 평가하는 또 다른 방법을 제공하기 때문에 중요합니다. 이는 다음 연습 문제에서 확인하게 될 거예요.

이 연습 문제 세트(총 3개)에서는 최종 BFS 알고리즘에 도달할 수 있도록 단계적으로 구축해 나갑니다. 문제는 3개의 부분으로 나뉘어 있으며, 순서대로 완료하면 BFS 알고리즘의 1차 구현에 도달하게 될 거예요.

Instrukcje

100 XP
  • 세 개의 매개변수 G, node1, node2를 받으며 두 노드 사이에 경로가 존재하는지 여부를 반환하는 path_exists() 함수를 만드세요.
  • 방문할 노드의 큐를 첫 번째 노드 node1로 초기화하세요. queue는 리스트여야 합니다.
  • queue의 노드들을 반복(iterate)하세요.
  • 그래프 G의 .neighbors() 메서드를 사용해 해당 노드의 이웃을 가져오세요.
  • 목적지 노드 node2가 neighbors 집합에 있는지 확인하세요. 있다면 True를 반환하세요.