图论算法小结:欧拉回路
欧拉回路
欧拉回路是指在一个图G中,从起点s出发,不重复地经过所有边后又返回到起点s的一条路径。同样还有关于欧拉道路的定义,不过起点和终点不一定重合,但都是不重复地经过图中的每一条边。
判断一个图中是否存在欧拉回路(道路)通过以下条件来判断:
(1)如果图G是一个无向图,那么度数为奇数的点不能超过两个,且这两个点其中一个作为起点,另一个作为终点。如果度数均为偶数,那么所有点均可以作为起点或终点。
(2)如果图G是一个无向图,那么度数为奇数的点不能超过两个,且这两个点中入度比出度小1的点必须作为起点,另一个入度比出度大1的点必须作为终点。如果度数均为偶数,那么所有点均可以作为起点或终点。
寻找欧拉回路实际上利用的还是DFS,只不过要求了不重复经过每一条边,因此需要设置一个标记数组,标记哪些边已经被使用过,每次只能通过未使用的边来拓展新的结点。
下面的代码给出了用邻接表实现的寻找欧拉回路的方法,最终欧拉回路被放入数组中,起点在数组尾部,终点在数组头部。
#define N 1000 typedef pair<int, int>P; queue<P>q[N];//图的邻接表存储,first表示结点编号,second表示路径编号 struct Edge { int from, to; }path[N];//欧拉回路 int vis[N];//标记路径序号 int top, E;//top是path数组的个数,E是边数,初始设置为0 void addedge(int u, int v) { q[u].push(P(v, ++E)); q[v].push(P(u, E)); } void euler(int u) { int v; while (!q[u].empty()) { P p = q[u].front(); q[u].pop(); v = p.first; if (vis[p.second])continue; vis[p.second] = 1;//标记路径 euler(v); path[++top].from = u; path[top].to = v; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。