График, где DFS и BFS не MST

Question

Мне нужно найти связанный, неориентированный, взвешенный граф и начальную вершину, где ни BFS, ни DFS не являются MST. независимо от порядка следования смежности.

Answer 1

Толстые ребра имеют вес 100, тонкие ребра имеют вес 1. Начало от средней вершины.

Верхний треугольник - ловушка BFS. BFS выберет оба толстых края, в то время как MST будет содержать только один.

Нижний треугольник - ловушка DFS. DFS выберет толстый край, в то время как MST не будет его содержать.

Общий вес MST: 103

Вес дерева DFS: 202

Вес дерева BFS: 202

Альтернативный пример с деревьями MST 103 и BFS / DFS (начиная с самой верхней вершины) 202: