相关疑难解决方法(0)

如何从有向图中找到(迭代)有向图中的所有周期？

例如,我想要这样的东西:

A->B->A
A->B->C->A

但不是:B-> C-> B.

这是一个消费税:

考虑从加权连通图G中找到边的最小权重连接子集T的问题.T的权重是T中所有边权重的总和.给计算最小权重连通子集T的有效算法.

这是我得到的:

1. 我必须假设权重由正面和负面混合.只有两种重量的混合才能对这种消费有意义.

2. 我将首先对边缘进行排序,因此负边缘将首先出现.

3. 我会考虑使用Kruskal的算法,但应该进行一些修改

4. 因为我欢迎负边缘,我会尝试添加尽可能多的负边缘.

5. 另外,可以添加一些正边缘以便在不是所有负边缘都连接的情况下它们可能需要一些正边缘作为桥接.

好的,上面是我的想法.但是当我试图弄脏手时,我就陷入了困境.

如何始终记录可能的最小重量？

例如,

{0,1}的权重为-20

{2,3}的重量为-10

如果{1,3}的权重为11,那么我当然不希望{1,3}

或者如果{1,3}的重量为9,那么我想要

通过什么样的数据结构,我可以始终保持最小权重和该权重的顶点？

值得注意的是,这个消费的子集寻求的目标edges.

考虑从加权连通图G 中找到边缘的最小权重连接子集T的问题

这意味着仍然需要包含所有顶点.

它也不仅仅是一个MST.考虑如果顶点有两条边,一条是-1,另一条是-2.在普通的MST算法中,只会采用-2的边缘.但在这个消费税中,需要采取-1和-2来进一步降低总体重量.