um=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语言算法:Рint count=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; Р } Р}
全文预览
