2
그래프의 BFS 및 DFS 트리가 최소 스패닝 트리가 아니고 인접성 목록의 순서가 중요하지 않다고 묻는 질문이 있습니다. BFS DFS와 MST의 속성은 있지만 혼란 스럽습니다. 문제에 어떻게 접근해야합니까? (해결책을 찾지 못함)특정 조건을 기반으로 그래프 만들기
A
답변
0
제안 사항은 그래프에서 MST를 찾는 알고리즘을 살펴보고 왜 이것이 BFS 또는 DFS 검색이 아닌지 생각하는 것입니다.
모든 알고리즘에서 까다로운 부분을 실제로 테스트하는 엣지 케이스를 찾는 것이 구현의 중요한 부분입니다. 간단한 예제로 시작하여 간단한 BFS/DFS 검색을 실패하게 만드는 방식으로 새로운 가장자리를 추가하거나 입력을 변경해보십시오.
인접성 목록 순서와 관계가 없어야한다는 조건은 테스트 그래프가 자연히 알고리즘에 가장자리를 잘못 공급하는 방식이 아닌, 매우 어려운 구조를 갖도록하는 것입니다.
1
k 정점에 대한 전체 그래프를 상상해보십시오. k > 3의 경우 DFS 트리는 항상 BFS 트리와 다르게 보입니다. k > 4의 경우 BFS 및 DFS 트리와 다른 MST을 사용할 수 있습니다. MST의 모양을 DFS 트리와 다르게 선택할 수 있습니다. 하나의 꼭지점에서 3 개의 가장자리가 나오게해야합니다. MST의 모양을 BFS 트리와 다르게 선택할 수 있습니다. 정점에 세 개 이상의 가장자리가 나오지 않도록하십시오. 선택한 가장자리를 만들기 위해 가중치를 지정하고 MST의 일부인 가장자리 만 지정하여 MST의 모양을 선택합니다. 다섯 개 꼭지점
DFS Tree
1-----2----3
|
|
4-----5
BFS Tree
1
____|____
//\ \
2 3 4 5
MST
2
|
1---3---5
|
4
완전한 그래프 5를 갖는다 * 2분의 4 = 4 개만 어떤 트리 필요한있는 에지 (10).
나중에 최단 경로 알고리즘이나 다른 것을 실행하도록 요청 받는지 정확하게 알 수 있습니까? 그러나 그래프의 구조를 변경할 수는 없으며 그래프가 트리인지 아닌지에 따라 입력 값이 달라집니다. –