• 欢迎光临~

欧拉路/欧拉回路

开发技术 开发技术 2022-10-04 次浏览

欧拉路:

从起点出发,不重复的走完所有边,称为欧拉路

存在条件:

1)图是连通的;

2)对于无向图,有且仅有两个点的度为奇数,其它点的度均为偶数,或所有的点的度均为偶数;

3)对于有向图,除去起点和终点,所有点的入度和出度都相等,起点出度比入度大1,终点入度比出度大1。

代码:

 1 int n,ans,p;
 2 void DFS(int x)
 3 {
 4     for(int i=1;i<=n;i++)  //顺序找可以访问的边,优先找节点最小的
 5     {
 6         if(e[x][i])            //若这条边未被访问过
 7         {
 8             e[x][i]--;    //删去这一条边,防止重复访问
 9             e[i][x]--;    //针对无向图
10             DFS(i);
11         }
12     }
13     ans[++p]=x;              //将访问的节点存入答案数组(逆过程)
14 }

欧拉回路:

即起点和终点在一起的欧拉路。

 

程序员灯塔
转载请注明原文链接:欧拉路/欧拉回路
喜欢 (0)