[关闭]
@xzyxzy 2018-04-01T09:27:46.000000Z 字数 363 阅读 635

欧拉路

图论


理解

无向图的一笔画问题

判断

若一个点连的边的条数为奇数,则称之为奇点

一个图有且仅有两个奇点,构成欧拉路

一个图没有奇点,构成欧拉回路(起点与终点重合)

路径记录!!

不太会,大概就是:
把经过的边删掉,然后在递归最后记录路径,反向输出

题目

所以Thanks to yyb&LSH
为了字典序最小,要按字典序搜
为了构成欧拉路,要放在递归之后记录路径,倒序输出,最先搜到的字典序最小,所以递归之后保存路径可以使得字典序小的排在后面,输出中靠前
//自己这么理解吧,如果搜字典序最小的点搜不成环,最后回不到那个点,然后肯定先搜构成环的路使得这是一条欧拉路,所以要先搜先放后输出
(如果不理解有一个图的,可以去马克飞象看看)

哈密顿回路

指不重复地走过所有的点并最终能回到起点的回路(深搜算法)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注