그래프 순회

깊이 우선과 너비 우선은 그래프를 탐색하는 두 가지 일반적인 방법입니다.
그래프 순회는 그래프의 각 꼭지점을 정확히 한 번씩 방문하는 과정입니다. 그래프를 탐색하는 두 가지 인기 있는 방법은 깊이 우선 탐색(또는 깊이 우선 탐색)과 너비 우선 탐색(또는 폭)입니다. -첫번째 검색). 두 순회 모두 아래 그림과 같이 클래스를 사용하여 모델링할 수 있는 스패닝 트리를 생성합니다. Tree는 AbstractGraph 클래스에 정의된 내부 클래스입니다. AbstractGraph.Tree는 요소 검색에서 정의한 Tree 인터페이스와 다릅니다. AbstractGraph.Tree는 노드의 부모-자식 관계를 설명하기 위해 설계된 특수 클래스인 반면, Tree 인터페이스는 트리에서 검색, 삽입, 삭제와 같은 일반적인 작업을 정의합니다. 스패닝 트리에 대해 이러한 작업을 수행할 필요가 없으므로 AbstractGraph.Tree는 Tree.

Tree 클래스는 AbstractGraph.java의 226~293행에 있는 AbstractGraph 클래스의 내부 클래스로 정의됩니다. 생성자는 루트, 가장자리 및 검색 순서가 포함된 트리를 생성합니다.

Tree 클래스는 7가지 메소드를 정의합니다. getRoot() 메서드는 트리의 루트를 반환합니다. getSearchOrder() 메소드를 호출하여 검색된 정점의 순서를 얻을 수 있습니다. getParent(v)를 호출하여 검색에서 정점 v의 상위를 찾을 수 있습니다. getNumberOfVerticesFound()를 호출하면 검색된 정점 수를 반환합니다. getPath(index) 메소드는 지정된 정점 인덱스에서 루트까지 정점 목록을 반환합니다. printPath(v)를 호출하면 루트에서 v까지의 경로가 표시됩니다. printTree() 메서드

위 내용은 그래프 순회의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!