有向图问题的算法

Question

请帮我解决以下问题的算法 -

鉴于一系列事实,我们希望尽可能多地消除冗余.该问题涉及的事实是大写字母之间的传递关系的成员.因此,每个事实都是一对大写字母,例如AB,意味着A与B相关.一个字母可能与自身相关,也可能不相关,但是传递性成立:如果A与B相关,而B与C相关,那么我们可以推断A与C相关.创建一个FactCount类,它包含一个方法minFacts,它被赋予一个已知的String []并返回最小的事实集合的大小,这些事实将允许我们推断所有(并且只有那些东西)可以从已知的事实中推断出来.

已知的每个元素将包含由单个空格分隔的1个或多个事实.最小的一组事实可能包含可从已知但未包含在其中的事实.

例如:

{"AB AC CA AA BC","AD"}

返回:4

AB,CA,BC和AD允许我们推断AA(AB,BC,CA通过传递性给出AA)和AC(AB,BC通过传递性给出AC),并且没有更小的子集允许我们推断所有已知事实.

PS - 它不是功课.只是我在网上找到的一个问题,几个小时都无法解决...

Answer 1

在我看来,您正在寻找图形的生成树.

连通图G的生成树也可以定义为不包含循环的G的最大边集,或者作为连接所有顶点的最小边集.

从生成树中,您可以获得图表的最小表示.任何其他边缘的添加将创建一个循环,因此节点之间的关系的冗余信息.

另请注意,如果在算法结束时,您还有剩余的未连接节点(意味着图表中有MST不接触的节点),则表示您获得的生成树是一个独立的实体,并且没有关系(边缘)连接生成树的节点和不在其中的节点.

在更多的数学术语中,属于您的生成树的节点和不属于它的节点是不相交的集合,并且它们都不是空集.

您当然可以在剩余子集上再次执行MST搜索以生成生成林,直到耗尽节点集.