欧拉图、哈密顿图
欧拉图
定义
通过图中所有边恰好一次且行遍所有顶点的 通路 称为欧拉通路。
通过图中所有边恰好一次且行遍所有顶点的 回路 称为欧拉回路。
具有欧拉回路 的无向图或有向图称为 欧拉图 。
具有欧拉通路但不具有欧拉回路 的无向图或有向图称为 半欧拉图 。
非形式化地讲，欧拉图就是从 任意一个点 开始都可以一笔画完整个图，半欧拉图必须从 某个点 开始才能一笔画完整个图 。
求欧拉回路 \(/\) 欧拉通路
常用的是 \(\operatorname{Hierholzer}\) 算法，也称逐步插入回路法 。
从一条回路开始，每次任取一条目前回路中的点，将其替换为一条简单回路，以此寻找到一条欧拉回路。如果从路开始的话，就可以寻找到一条欧拉路。
优化：将找回路的 \(\operatorname{DFS}\) 和 \(\operatorname{Hierholzer}\) 算法的递归合并，边找回路边使用 \(\operatorname{Hierholzer}\) 算法。
时间复杂度：\(O(n+m\log m)\)
核心代码：（例题如：P1341 无序字母对 、P2731 [USACO3.3]骑马修栅栏 ）
#define Maxn 100005
#define Maxm 200005
int n,m,tot,cnt,rt=inf,tp;
int hea[Maxn],nex[Maxm],ver[Maxm];
int deg[Maxn],sta[Maxm];
struct Data { int From,To; }Edge[Maxm];
void dfs(int x,int D)
{
if(hea[x]>0) for(int i=hea[x];i && hea[x];i=nex[i])
hea[x]=nex[i],dfs(ver[i],D+1); // hea 要在循环内判断
sta[++tp]=x; // 及时舍去已经走过的路径！！！
}
bool cmp(Data x,Data y)
{
if(x.From!=y.From) return x.From<y.From;
return x.To>y.To;
}
n=rd(),m=rd();
for(int i=1,x,y;i<=m;i++) x=rd(),y=rd(),Edge[i]=(Data){x,y},deg[x]++,deg[y]--,rt=min(rt,min(x,y));
sort(Edge+1,Edge+m+1,cmp);
for(int i=1;i<=m;i++) add(Edge[i].From,Edge[i].To);
for(int i=1;i<=n;i++)
{
if(deg[i]) cnt++,rt=(deg[i]>0)?i:rt;
if(deg[i]<-1 || deg[i]>1) cnt=inf;
}
if(cnt!=0 && cnt!=2) printf("No\n");
else
{
dfs(rt,0);
for(int i=tp;i>=1;i--) printf("%d ",sta[i]);
printf("\n");
}
哈密顿图
版权声明：本文为EricQian原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。