DFS和BFS不是MST的图

问题描述 投票：0回答：1

我需要找到一个连接的，无向的加权图和一个起始顶点，其中BFS和DFS都不是MST。无论其邻接列表的顺序如何。

graph breadth-first-search dfs
1个回答
0
投票

Hourglass example

厚边的权重为100，薄边的权重为1。从中间顶点开始。

[上部三角形是BFS陷阱。 BFS将选择两个粗边，而MST仅包含一个。

下三角是DFS陷阱。 DFS将选择粗边，而MST将不包含粗边。

MST总重量：103

DFS树权重：202

BFS树权重：202

带有MST 103和BFS / DFS树（从最高顶点开始）202的替代示例：

Pentagon example

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.