高手请进,与无向图回路有关的问题

已知一个无向连通图,欲找出图中所有不能构成回路的线,求效率较高的方法.

6 个解决方案

#1

所求路径可能要加一个'从叶到叶'的条件,才有较大意义,否则,单个一条边,也是不能构成回路的线了.
这样的问题我想不会有效率高的方法,但也不会有效率特别低的方法,只要可行,效率就不会有太多差别.

#2

这个问题不是求路径,各边和结点也不考虑权值,只想找出不能构成回路的线.

如下图: 要求的线是 CD,DE,DH,GK,KL.

      A         B            C      D         E
      *---------*------------*------*---------*
      |         |            |      |
      |         |    I    J  |      |
    F *---------* G  *----*  |    H *
      |         |    |    |  |
      |         |    |    |  |
      |       K *----*----*  |
      |              L    M  |
    N *----------------------* O

#3

这一工作我以前具体做过,
1.CD,DE,DH的去除法: 反复寻找度数为1的点(叶).
这样循环次后，就依次可把ED,HD和DC除去．
2.GK,KL的去除法: 寻找割集为1的边.

#4

去叶共循环2次:
第一次,因E,H为叶,所以可去掉了ED,HD,
第一次循环结果,使D点成为叶,所以第二次去掉了DC.
第二次循环结果,就不再有叶了.

#5

zzwu(未名):
   非常感谢!
   1)"叶"点的去除用循环法感觉效率不高,暂且如此吧.
   2)GK,KL的去除法的算法能否详细告知.

#6

如GK,KL的判别，是须全局考虑问题，恐非局部能识别，算法效率不会很高。

#1

#2

#3