有向オイラー閉路問題
Posted: 2011年12月06日(火) 13:14
大学での研究課題なのですが、配列による隣接行列を使ってグラフ問題の、有向オイラー閉路を探索し、発見したら表示するプログラムを組んだつもりだったのですが、ある隣接行列では発見されるはずの経路が発見されず「解なし」と表示されてしまいました。コードは以下のとおりで、発見されるはずの経路は「0,1,2,4,9,2,5,10,4,8,0」「0,1,2,5,10,4,9,2,4,8,0」です。
他の隣接行列は自分のほうでは問題ありませんでした。例えば
なら、「0,1,2,5,2,4,0」と表示されました。
どうして、あの隣接行列はうまくいかないのかどうか教えてください。
#include <stdio.h>
#define Node 8 /* 頂点の数 */
#define Root 10 /* 辺の数 */
#define Start 0 /* 開始点 */
/* 0 1 2 3 4 5 6 7 8 9101112131415 */
int a[16][16]={{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 1 */ {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 2 */ {0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0},
/* 3 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 4 */ {0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0},
/* 5 */ {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
/* 6 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 7 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 8 */ {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 9 */ {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 10 */ {0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0},
/* 11 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 12 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 13 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 14 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/* 15 */ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
int success,
v[Root+1], /* 経路を入れるスタック */
x[Root+1],
n; /* 通過した道の数 */
void visit(int);
int main(void)
{
success=0; n=0;
visit(Start);
if (success==0)
printf("解なし\n");
}
void visit(int i)
{
int j;
v[n]=i;
if (n==Root && i==Start){ /* 辺の数だけ通過し元に戻ったら */
printf("解 %d:",++success);
for (i=0;i<=Root;i++)
printf("%d,",v[i]);
printf("\n");
}
else {
for (j=0;j<=Node;j++)
if (a[i][j]!=0){
a[i][j]--; /* 通った道を切り離す */
n++;
visit(j);
a[i][j]++;
n--;
}
}
}
int a[8][8]={{0,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0},
{0,0,0,0,1,1,0,0},
{0,0,0,0,0,0,0,0},
{1,1,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}};
どうして、あの隣接行列はうまくいかないのかどうか教えてください。