admin 管理员组

文章数量: 888526

欧拉回路判断

.htm

.html

求欧拉回路的一种解法
　　下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。
　　int num = 0;//标记输出队列
　　int match[MAX];//标志节点的度，无向图，不区分入度和出度
　　void solve(int x)
　　{
　　     if(match[x] == 0)
　　            Record[num++] = x;
　　     else
　　    {
　　           for(int k =1;k<=n;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。这个其实是个递归过程。

本文标签： 欧拉回路判断

版权声明：本文标题：欧拉回路判断 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686635372h20004.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。