欧拉回路

欧拉回路 【定义】 图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。 具有欧拉回路的图称为欧拉图（简称E图）。 【相关结论】 定理： 一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数或只有两个定点的度数为奇。 一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。 求欧拉回路的一种解法 下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。 int num = 0;//标记输出队列 int match[MAX];//标志节点的度，无向图，不区分入度和出度 void solve(int x) { if(match[x] == 0)

Record[num++] = x;

else { for(int k =0;k<=500;k++) { if(Array[x][k] !=0 ) { Array[x][k]–; Array[k][x]–; match[x]–; match[k]–; solve(k); }

} Record[num++] = x; } } 注意record中的点的排列是输出的到序，因此，如果要输出欧拉路径，需要将record倒过来输出。 求欧拉回路的思路： 循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。 具体步骤： 1。如果此时与该点无相连的点，那么就加入路径中 2。如果该点有相连的点，那马就列一张表，遍历这些点，知道没有相连的点。 3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。 4。这个其实是个递归过程。