Graph | Eulerian path

时间:2014-11-07 20:38:07   收藏:0   阅读:256

In graph theory, a Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex. 

Hierholzer‘s algorithm 可以在O(E)的时间下给出解。

算法:

当然,需要用到双向链表不断地把边删掉,如果最终所有边都被访问了,那么就可以退出了。但是如果找不到点继续扩展,而且边又还有的话,那么就说明给不出回路。

原文:http://www.cnblogs.com/linyx/p/4082227.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!