有向オイラー閉路問題

[Euler]

大学での研究課題なのですが、配列による隣接行列を使ってグラフ問題の、有向オイラー閉路を探索し、発見したら表示するプログラムを組んだつもりだったのですが、ある隣接行列では発見されるはずの経路が発見されず「解なし」と表示されてしまいました。コードは以下のとおりで、発見されるはずの経路は「0,1,2,4,9,2,5,10,4,8,0」「0,1,2,5,10,4,9,2,4,8,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}}; 

なら、「0,1,2,5,2,4,0」と表示されました。
どうして、あの隣接行列はうまくいかないのかどうか教えてください。

[beatle]

グラフ理論にそんなに強いわけではありませんが、少し調べたところ「オイラー路」はすべての辺を含む路のことですね。
あなたの示された隣接行列を見ると、辺は10よりも多い気がしますが、どうですか？

[Euler]

説明不足だったようです。すいません。
隣接行列で表されたグラフの部分グラフとして、最初に定義した頂点と辺の数の有向オイラー閉路が存在する場合に、それを表示するというものです。
その点は、自分でも不安がある部分なのですが、このプログラムのアルゴリズムは「深さ優先探索でRootで定義された辺の数だけ探索して開始点に戻ってきているか」で判断しているはずなので、大丈夫だと思っています。
実際に、

コード:

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}};

のときは

コード:

#define Node 5        /* 状態の数 */
#define Root 6        /* 辺の数 */
#define Start 0       /* 開始点 */

で、隣接行列の辺の数は定義されたRootの6より多い7ですが問題ありませんでした。

[beatle]

Nodeが8と定義されているので、8を超える番号のノードは調査されませんよね。
ですから10を含む「0,1,2,4,9,2,5,10,4,8,0」「0,1,2,5,10,4,9,2,4,8,0」の2つは
発見されないのが正解では？

[Euler]

ありがとうございます！
言われたとおりに下記のように修正したらきちんと表示されました！本当にありがとうございます。

コード:

～
for (j=0;j<=Root;j++)
            if (a[i][j]!=0){
                a[i][j]--;     /* 通った道を切り離す */
                n++;
                visit(j);
                a[i][j]++;
                n--;
            }
～

どうやら自分の拙い勘違いがあったようです。
解決に助力いただき本当にありがとうございます。

[beatle]

いやいや、Nodeの定義を変えるべきだと思ったのですが。
Nodeは頂点の数ですよね？そして頂点は0から15の16個あるわけですよね？

[non]

そういう課題ならそれでいいのでしょうが、釈然としませんよね。
使わない辺があることは、良しとしても、すべての辺を持つノードを通ったかはチェックしなくて良いのでしょうか。
通るべき辺の数Rootが与えられていることが、よくわからない。