哥尼斯堡七桥问题
七桥问题时18世纪著名古典数学问题之一. 在哥尼斯堡的一个公园里, 有七座桥将河中两个岛及岛与河岸连接起来, 问是否可能从这四块陆地中任一块出发, 恰好通过每座桥一次, 再回到起点
欧拉于1736年研究并解决了此问题, 并因此开创了数学的一个新的分支——图论与几何拓扑
欧拉回路和欧拉路径
① 对于无向图, 所有边都是联通的
\(\quad\) (1) 存在欧拉路径的充要条件: 度数为奇数的点只能有0或2个
\(\quad\) (2) 存在欧拉回路的充要条件: 度数为奇数的点只能有0个
② 对于有向图, 所有边都是联通的
\(\quad\) (1) 存在欧拉路径的充要条件: 要么所有点的出度均等于入度; 要么除了两个点之外, 其余所有点的出度等于入度, 剩余的两个点: 一个满足出度比入度多1(起点), 另一个满足入度比出度多1(终点)
\(\quad\) (2) 存在欧拉回路的充要条件: 所有点的出度均等于入度
//dfs暴搜欧拉路径
void dfs (int u)
{
for(int i=1;i<=n;i++)
if(g[u][i])
{
g[u][i]--,g[i][u]--;
dfs(i);
}
ans[++cnt]=u;
}
//ans数组逆序存储路径,需要倒序输出
for(int i=cnt;i;i--)cout<<ans[i]<<' ';