欧拉回路 [邻接矩阵]

【问题描述】在一个无向图中，一条包含所有边，且其中每一条边只经过一次的路径叫做欧拉通路。若这条路径的起点与终点为同一点，则为欧拉回路。请找出图中的欧拉回路。

判定一个图是否存在欧拉通路或欧拉回路：定理1：一个图有欧拉回路当且仅当它是连通的（即不包括0度的结点）且每个结点都有偶数度。

定理2：一个图有欧拉通路当且仅当它是连通的且除两个结点外，其他结点都有偶数度。

定理3：在定理2的条件下，含奇数度的两个结点中，一个必为欧拉通路的起点，另一个必为终点。

int G[N][N];  // 无向图的邻接矩阵。如果两点连通，则为1，否则为0 int cnt[N]; int circuit[N], pos; int start,oddnumber; void search(int i) {  for (int j=0; j<n; j++)   if (G[j]==1)   {    G[j]=G[j]=0;    search(j);   } circuit[pos++]=i; } bool find_circuit()      // 返回false表示无欧拉回路 {  start=oddnumber=0;  memset(cnt, 0, sizeof(cnt));  for (int i=0; i<n; i++)    // 统计结点入度   for (int j=0; j<n; j++)    cnt+=G[j]; for (int i=0; i<n; i++)   if (cnt%2==1)   {    start=i;    oddnumber=oddnumber+1;   }   if (oddnumber>2 || oddnumber==1)   return false;  else {   pos=0;   search(start);

for (int i=0; i<pos; i++)

   cout<<circuit<<"--->"<<endl;

}

return true;

}