use*_*240 1 c++ algorithm tree minimum-spanning-tree graph-algorithm
假设我们找到了一棵最小的生成树.现在,我们只需要在MST中从A到Z的路径.我们怎样才能在O(n ^ 2)时间内做到这一点？
我们从根A开始.然后我们查看Ax(其中x是任何顶点)形式的树中的所有边.
然后,我们发现:AB,AC,AD等......然后对于每一个,我们寻找形式的边缘:Bx,Cx,Dx ......这显然不是O(n ^ 2).
那么在给定MST的情况下找到路径A - > Z的更好/更有效的方法是什么？
谢谢
| 归档时间： |
|
| 查看次数： |
2953 次 |
| 最近记录： |