그래프 순회

깊이 우선과 너비 우선은 그래프를 탐색하는 두 가지 일반적인 방법입니다.
그래프 순회는 그래프의 각 꼭지점을 정확히 한 번씩 방문하는 과정입니다. 그래프를 탐색하는 두 가지 인기 있는 방법은 깊이 우선 탐색(또는 깊이 우선 탐색)과 너비 우선 탐색(또는 폭)입니다. -첫번째 검색). 두 순회 모두 아래 그림과 같이 클래스를 사용하여 모델링할 수 있는 스패닝 트리를 생성합니다. 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!