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 语言算法: i nt count=0,cur=0,r[ N ][N]; // r[N ][N] 为图的邻接矩阵, cur 为当前结点编号, coun t 为欧拉路的数量。 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; }}
全文预览
