收集的C语言算法程序

求解欧拉回路的算法应该会有很多吧,但我目前掌握的算法只有两种,一是usaco上提供的,还有一种是在离散数学书上看到的fleury算法: 
1.usaco上提供的算法: 
# circuit is a global array
    find_euler_circuit
      circuitpos = 0
      find_circuit(node 1)
 
# nextnode and visited is a local array
# the path will be found in reverse order
  find_circuit(node i)
 
     if node i has no neighbors then
       circuit(circuitpos) = node i
       circuitpos = circuitpos + 1
     else
       while (node i has neighbors)
           pick a random neighbor node j of node i
           delete_edges (node j, node i)
           find_circuit (node j)
       circuit(circuitpos) = node i
       circuitpos = circuitpos + 1



总结: 这种算法的时间复杂度是o(e)的,空间复杂度也是o(e)的,这种算法的特点是最后倒序输出,这个地方需要特别重视一下,在图有欧拉通路或者有欧拉回路的时候,我们总可以从一个合适的点出发,找到一条欧拉路.可以做一下usaco的3.1的题目.


2.fleury算法:

(1).任取v0属于v(G),令P0=v0;

(2) 设Pi=v0e1v1e2…eivi已经行遍,按下面方法来从E(G)-{e1,e2,…..ei}中任取ei+1 ;

(a) : ei+1与vi相关联:

(b): 除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2,….ei}中的桥.

(3): 当(2)不能再进行时,算法停止. 

可以证明,当算法停止时所得的简单回路Pm=v0e1v1e2….emvm(vm=vo)为G中的一条欧莱回路.

总结:这种算法的复杂度是o(e*e),相队于前面那种算法在时间上没有什么优势,但是由于他是顺序找的,所以用这个来求解题目有时候会收到奇效,比如说题目要求欧拉回路字典序最小,先前的哪一种算法扎这个时候可能无能为力,但是用这个算法仍旧能够漂亮的解决这个问题    

大家可以参考一下pku的2337,一道很好的用fleury算法求解的题目