在图表中寻找方法

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

我有一个问题,因为我有一个任务是在非循环无向图中查找由奇数条边连接的调用对的数量。

我的问题是为什么我应该从那些具有奇数度数的顶点开始搜索图? 或者也许我从 ood 开始或什至都没关系

algorithm math charts
1个回答
0
投票

非循环连通图是一棵树。如果不相连,那么它就是一片森林,是树木的集合。

我假设它已连接,但如果没有,请将其应用于每棵树。

  • 摘任意一片叶子。
  • 从叶子运行 BFS,计算距叶子偶数和奇数距离的节点数,并将起始叶子包含在距其偶数距离的节点计数中。
  • return (奇数距离节点的数量) * (偶数距离节点的数量)
© www.soinside.com 2019 - 2024. All rights reserved.