Fin*_*fin 5 algorithm graph greedy
在我开始之前,是的,这是一个功课.如果我在最近的14个小时里没有尽力解决这个问题并且无处可去,我就不会在这里发布.
问题如下:我想检查是否可以从连接的无向图中删除边,而不是在O(V)时间内断开它,而不仅仅是线性的.
到目前为止我所达到的目标:
可以在不断开图形的情况下移除循环边缘,因此我只需检查图形是否具有循环.我有两种方法可以使用,一种是DFS,然后检查我是否有后边缘; 另一种是通过计算Vs和Es并检查是否| E | = | V | - 1,如果那是真的那么图是一棵树,我们可以删除没有节点而不断开它.
以前的两种方法都解决了这个问题,但两者都需要O(| E | + | V |),书中说有更快的方法(这可能是一种贪婪的方法).
我可以得到任何提示吗？
编辑:更具体地说,这是我的问题; 给定一个连通图G =(V,E),我可以删除E中的一些边e并使结果图仍然连接吗？
图形的任何递归遍历,在访问过程时标记节点,如果遇到已经标记的节点,则短路返回true将会起作用.如果没有可以移除的边缘,则需要O(| V |)遍历整个图形,如果它提前停止返回true,则需要更少的时间.
编辑
是的,整个图形的重复遍历需要O(| V | + | E |)时间,但是如果没有循环,我们只遍历整个图形 - 在这种情况下| E | = | V | -1,只需要O(| V |)时间.如果有一个循环,我们将在遍历最多| V |之后找到它 边(最多访问| V | +1个节点),同样需要O(| V |)时间.
此外,显然当从节点(第一个节点除外)进行遍历时,您不会考虑用于到达节点的边缘,因为这会导致您立即看到已访问过的节点.