实验六欧拉图判定和应用

【实验目的】掌握判断欧拉图的方法。

【实验内容】编程随机生成n个结点的无向图（有向图）并能进行（半）欧拉图的判定，若是则给出所有欧拉路.

【要求】对给定n个结点，随机生成邻接矩阵以确定某无向简单图（有向图）并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。

【实验原理和方法】

是根据随机生成的图求欧拉（回）路，先要随机生成一个邻接矩阵，然后判定是否是欧拉回路只要根据奇数度结点的个数。再用一个递归函数找出欧拉路。

 

 

 

（1）用关系矩阵R=表示图。

（2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。

    C语言算法：

  flag=1;

  for(i=1;i<=n && flag;i++)

  {

      sum=0;

      for(j=1;j<=n;j++)

          if(r[i][j]) sum++;

      if(sum%2==0) flag=0;

  }

  如果 flag  该无向图是欧拉图

（3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。

C语言算法：

flag=1;

for(i=1;i<=n && flag;i++)

{

    sum1=0;

    sum2=0;

    for(j=1;j<=n;j++)

        if(r[i][j]) sum1++;

    for(j=1;j<=n;j++)

        if(r[j][i]) sum2++;

    if(sum1%2==0 || sum2%2==0) flag=0;

}

如果 flag  该有向图是欧拉图

（4）求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。

C语言算法：

intcount=0,cur=0,r[N][N]; // r[N][N]为图的邻接矩阵，cur为当前结点编号，count为欧拉路的数量。

int sequence[M];// sequence保留访问点的序列，M为图的边数

输入图信息;

void try1(int k) //k表示边的序号

{

    int i,pre=cur; //j保留前一个点的位置,pre为前一结点的编号

    for (i=0;i<N;i++)

        if (r[cur][i]) //当前第cur点到第i点连通

           {

//删除当前点与第i点的边，记下第k次到达点i，把第i个点设为当前点

               r[cur][i]=0;cur=sequence[k]=i; 

               if (k<M) try1(k+1); //试下一个点

               else prt1();//经过了所有边，打印一个解

//上面条件不满足，说明当前点的出度为0，回溯，试下一位置

               r[pre][i]=1;cur=pre; 

           }

}

附上代码：

有向图：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. int n,a[100][100],m=0,visit[100];
  6. int cur=0,s[100],vis[100][100];
  7. void try1(int k)//取欧拉路
  8. {
  9.     int i;
  10.     if(cur==m+1)
  11.     {
  12.         for(i=0;i<cur;i++)
  13.         {
  14.             if(i==0)
  15.                 printf("%d",s[i]+1);
  16.             else
  17.                 printf("->%d",s[i]+1);
  18.         }
  19.         printf("\n");
  20.     }
  21.     else
  22.     {
  23.         for(i=0;i<n;i++)
  24.         {
  25.             if(a[k][i]&&!vis[k][i])
  26.             {
  27.                 vis[k][i]=1;
  28.                 vis[i][k]=1;
  29.                 s[cur++]=i;
  30.                 try1(i);
  31.                 cur--;
  32.                 vis[k][i]=0;
  33.                 vis[i][k]=0;
  34.             }
  35.         }
  36.     }
  37. }
  38. void dfs(int k)
  39. {
  40.     int i;
  41.     visit[k]=1;
  42.     for(i=0;i<n;i++)
  43.     {
  44.         if(a[k][i]&&!visit[i])
  45.         {
  46.             dfs(i);
  47.         }
  48.     }
  49. }
  50. int fun()//判断连通性
  51. {
  52.     int i;
  53.     dfs(0);
  54.     for(i=0;i<n;i++)
  55.     {
  56.         if(!visit[i])
  57.             return 0;
  58.     }
  59.     return 1;
  60. }
  61. int main(void)
  62. {
  63.     int i,j;
  64.     memset(vis,0,sizeof(vis));
  65.     memset(visit,0,sizeof(visit));
  66.     srand(time(NULL));
  67.     printf("请输入节点个数n：");
  68.     scanf("%d",&n);
  69.     for(i=0;i<n;i++)
  70.     {
  71.         for(j=0;j<n;j++)
  72.         {
  73.             if(i==j)
  74.                 a[i][j]=0;
  75.             else if(i>j)
  76.                 a[i][j]=a[j][i];
  77.             else
  78.                 a[i][j]=rand()%2;
  79.             m+=a[i][j];
  80.         }
  81.     }
  82.     m/=2;
  83.     printf("邻接矩阵为：\n ");
  84.     for(i=0;i<n;i++)
  85.     {
  86.         printf(" %d",i+1);
  87.     }
  88.     printf("\n");
  89.     for(i=0;i<n;i++)
  90.     {
  91.         printf("%d",i+1);
  92.         for(j=0;j<n;j++)
  93.             printf(" %d",a[i][j]);
  94.         printf("\n");
  95.     }
  96.     if(fun()==0)
  97.     {
  98.         printf("该图不是连通图！\n");
  99.         return 0;
  100.     }
  101.     printf("该图是连通图！\n");
  102.     int odd=0;
  103.     for(i=0;i<n;i++)
  104.     {
  105.         int sum=0;
  106.         for(j=0;j<n;j++)
  107.         {
  108.             if(a[i][j])
  109.                 sum++;
  110.         }
  111.         if(sum%2)
  112.             odd++;
  113.     }
  114.     if(odd==0)
  115.     {
  116.         printf("该图没有奇数度节点，具有欧拉回路，是欧拉图。\n");
  117.         printf("所有的欧拉路为：\n");
  118.         for(i=0;i<n;i++)
  119.         {
  120.             s[cur++]=i;
  121.             try1(i);
  122.             cur--;
  123.         }
  124.     }
  125.     else if(odd==2)
  126.     {
  127.         printf("该图有两个奇数度节点，具有欧拉路，是半欧拉图。\n");
  128.         printf("所有的欧拉路为：\n");
  129.         for(i=0;i<n;i++)
  130.         {
  131.             int sum=0;
  132.             for(j=0;j<n;j++)
  133.                 sum+=a[i][j];
  134.             if(sum%2)//起点或中点
  135.             {
  136.                 s[cur++]=i;
  137.                 try1(i);
  138.                 cur--;
  139.             }
  140.         }
  141.     }
  142.     else
  143.     {
  144.         printf("不是欧拉图,也不是半欧拉图\n");
  145.     }
  146.     return 0;
  147. }

无向图：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. int n,a[100][100],m=0,visit[100];
  6. int cur=0,s[100],vis[100][100];
  7. void try1(int k)//取欧拉路
  8. {
  9.     int i;
  10.     if(cur==m+1)
  11.     {
  12.         for(i=0;i<cur;i++)
  13.         {
  14.             if(i==0)
  15.                 printf("%d",s[i]+1);
  16.             else
  17.                 printf("->%d",s[i]+1);
  18.         }
  19.         printf("\n");
  20.     }
  21.     else
  22.     {
  23.         for(i=0;i<n;i++)
  24.         {
  25.             if(a[k][i]&&!vis[k][i])
  26.             {
  27.                 vis[k][i]=1;
  28.                 s[cur++]=i;
  29.                 try1(i);
  30.                 cur--;
  31.                 vis[k][i]=0;
  32.             }
  33.         }
  34.     }
  35. }
  36. void dfs(int k)
  37. {
  38.     int i;
  39.     visit[k]=1;
  40.     for(i=0;i<n;i++)
  41.     {
  42.         if(a[k][i]&&!visit[i])
  43.         {
  44.             dfs(i);
  45.         }
  46.     }
  47. }
  48. int fun()//判断连通性
  49. {
  50.     int i,j;
  51.     for(i=0;i<n;i++)
  52.     {
  53.         memset(visit,0,sizeof(visit));
  54.         dfs(i);
  55.         for(j=0;j<n;j++)
  56.         {
  57.             if(!visit[j])
  58.                 break;
  59.         }
  60.         if(j==n)
  61.             return 1;
  62.     }
  63.     return 0;
  64. }
  65. int main(void)
  66. {
  67.     int i,j;
  68.     memset(vis,0,sizeof(vis));
  69.     srand(time(NULL));
  70.     printf("请输入节点个数n：");
  71.     scanf("%d",&n);
  72.     for(i=0;i<n;i++)
  73.     {
  74.         for(j=0;j<n;j++)
  75.         {
  76.             a[i][j]=rand()%2;
  77.             m+=a[i][j];
  78.         }
  79.     }
  80.     printf("邻接矩阵为：\n ");
  81.     for(i=0;i<n;i++)
  82.     {
  83.         printf(" %d",i+1);
  84.     }
  85.     printf("\n");
  86.     for(i=0;i<n;i++)
  87.     {
  88.         printf("%d",i+1);
  89.         for(j=0;j<n;j++)
  90.             printf(" %d",a[i][j]);
  91.         printf("\n");
  92.     }
  93.     if(fun()==0)
  94.     {
  95.         printf("该图不是连通图！\n");
  96.         return 0;
  97.     }
  98.     printf("该图是连通图！\n");
  99.     int odd=0,begin=-1,end=-1;
  100.     for(i=0;i<n;i++)
  101.     {
  102.         int sum1=0,sum2=0;
  103.         for(j=0;j<n;j++)
  104.         {
  105.             sum1+=a[i][j];
  106.             sum2+=a[j][i];
  107.         }
  108.         if(sum1!=sum2)
  109.         {
  110.             odd++;
  111.             if(sum1-sum2==1)
  112.                 begin=i;
  113.             if(sum2-sum1==1)
  114.                 end=i;
  115.         }
  116.     }
  117.     if(odd==0)
  118.     {
  119.         printf("该图所有点出度等于入度，具有欧拉回路，是欧拉图。\n");
  120.         printf("所有的欧拉路为：\n");
  121.         for(i=0;i<n;i++)
  122.         {
  123.             s[cur++]=i;
  124.             try1(i);
  125.             cur--;
  126.         }
  127.     }
  128.     else if(odd==2&&begin!=-1&&end!=-1)
  129.     {
  130.         printf("该图有两个奇数度节点，具有欧拉路，是半欧拉图。\n");
  131.         printf("所有的欧拉路为：\n");
  132.         s[cur++]=begin;
  133.         try1(begin);
  134.     }
  135.     else
  136.     {
  137.         printf("不是欧拉图,也不是半欧拉图\n");
  138.     }
  139.     return 0;
  140. }

 

过一学期了第一次写离散作业

版权声明：本文为zhaohongjie原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/zhaohongjie/p/12950870.html