시작하기무료로 시작하기

최단 경로 I

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

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

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

이 연습은 강의의 일부입니다

Python으로 시작하는 네트워크 분석

강의 보기

연습 안내

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

실습형 인터랙티브 연습

이 예제를 이 샘플 코드를 완성하여 풀어보세요.

# Define path_exists()
def ____:
    """
    This function checks whether a path exists between two nodes (node1, node2) in graph G.
    """
    visited_nodes = set()

    # Initialize the queue of nodes to visit with the first node: queue
    queue = ____

    # Iterate over the nodes in the queue
    for node in ____:

        # Get neighbors of the node
        neighbors = ____

        # Check to see if the destination node is in the set of neighbors
        if node2 in ____:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return ____
            break
코드 편집 및 실행