オイラー小路を求めるプログラム

[きっか]

　オイラー小路（一筆書き）を求めるプログラムをＣ言語で書きたいのですが困っています。
まず、オイラーグラフかどうかを判定するプログラムは書くことができました。
その後にオイラーグラフならばオイラー小路を求めたいのですが、上手くいきません。
どうすればよいでしょうか？

#include <stdio.h>
#define MAX 10
int a[MAX][MAX];
int n;
int route[MAX]; /* 経路を記憶 */
int Vflag[MAX]; /* すでに通った点を記憶 */
int Eflag[MAX];

int euler(){
int c[MAX];
int i,j,count,odd=0;
int comma;


for(i=0;i<n;i++){
count = 1;
for(j=0;j<n;j++){
if(a[j] == 1){
c = count++;
}
}
}
for(i=0;i<n;i++){
if(c % 2 == 1){ //奇数だったら
odd++;
}
}

if(odd == 0 || odd == 2){ // 奇数の次数を持つ頂点が０か2個か判定
printf("Your graph is Euler\n\n");
printf(" a b c d\n");
for(i=0;i<n;i++){
printf("%c ",'a'+i);
for(j=0;j<n;j++){
printf("%d ",a[j]);
}
printf("\n");
}
return 0;
}else{
printf("Your graph isn't Euler\n");
return 1;
}
}

void tansaku(int k){
int i;

if (n==k) { /* 全点を通った */
printf("%d", route[0]);
for (i=1; i<n; i++) printf("-%d",route);
} else { /* 次の点を探して移動 */
for (i=0; i<n; i++) {
if (Vflag==0) {
Vflag=1; route[k]=i;
tansaku(k+1);
Vflag=0; /* 元にもどす */
}
}
printf("\n");
}
}

int main(void){
int i,j;
int comma;


printf("Vertex\n");
scanf("%d",&n);
for (i=0; i<n; i++) Vflag=0;
for (i=0; i<n; i++) Eflag=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}

printf("V={");
comma=0;
for(i=0;i<n;i++){
if(comma){printf(",");}
printf("%c",'a'+i);
comma=1;
}
printf("},E={");
comma=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(a[i][j]){
if(comma){printf(",");}
printf("(%c,%c)",'a'+i,'a'+j);
comma=1;
}
}
}
printf("}\n");
euler();
tansaku(0);

return 0;
}

[box]

コメントがないために、用途がよくわからない変数が見受けられます。
それらの変数に関する説明をお願いできますか？

[きっか]

回答ありがとうございました。
コメント付けましたが、足りないところがあれば教えてください。

#include <stdio.h>
#define MAX 10
int a[MAX][MAX];
int n;/*頂点数*/
int route[MAX]; /* 経路を記憶 */
int Vflag[MAX]; /* すでに通った点を記憶 */

int euler(){
int c[MAX];/*辺の数を格納していく配列*/
int i,j;
int count;/*辺の数*/
int odd=0;/*辺の数が奇数であった頂点をカウントする*/

for(i=0;i<n;i++){
count = 1;
for(j=0;j<n;j++){
if(a[j] == 1){
c = count++;
}
}
}
for(i=0;i<n;i++){
if(c % 2 == 1){ //奇数だったら
odd++;
}
}

if(odd == 0 || odd == 2){ // 奇数の次数を持つ頂点が０か2個か判定
printf("Your graph is Euler\n\n");
printf(" a b c d\n");
for(i=0;i<n;i++){
printf("%c ",'a'+i);
for(j=0;j<n;j++){
printf("%d ",a[j]);
}
printf("\n");
}
return 0;
}else{
printf("Your graph isn't Euler\n");
return 1;
}
}

void tansaku(int k){
int i;

if (n==k) { /* 全点を通った */
printf("%d", route[0]);
for (i=1; i<n; i++) printf("-%d",route);
} else { /* 次の点を探して移動 */
for (i=0; i<n; i++) {
if (Vflag==0) {
Vflag=1; route[k]=i;
tansaku(k+1);
Vflag=0; /* 元にもどす */
}
}
printf("\n");
}
}

int main(void){
int i,j;
int comma;


printf("Vertex\n");
scanf("%d",&n);
for (i=0; i<n; i++) Vflag=0;
for (i=0; i<n; i++) Eflag=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}

printf("V={");
comma=0;
for(i=0;i<n;i++){
if(comma){printf(",");}
printf("%c",'a'+i);
comma=1;
}
printf("},E={");
comma=0;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(a[i][j]){
if(comma){printf(",");}
printf("(%c,%c)",'a'+i,'a'+j);
comma=1;
}
}
}
printf("}\n");
euler();
tansaku(0);

return 0;
}

[きっか]

実行結果
Vertex
4
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
0
V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,a),(b,d),(c,a),(c,d),(d,a),(b,d),(d,c)}
Your graph is Euler

a b c d
a 0 1 1 1
b 1 0 0 1
c 1 0 0 1
d 1 1 1 0

0-1-2-3　←問題点　一筆書きのプログラムにならず、ただ頂点を周回するだけとなっている。
0-1-3-2

0-2-1-3
0-2-3-1

0-3-1-2
以下、省略。

[mats]

再起で求めようとしているのはいいのですが，
・今どの点にいるのか考慮していない
・次の点までのエッジが貼られているかどうかを考慮していない
というのが問題だと思われます．

そもそもそれ以前に，オイラー路の定義は「すべての辺を一度ずつ使用する経路」だと思うのですが，
このプログラムの探索部分ではハミルトン路（「全ての頂点を一度ずつ使用する経路」）を求めているように見えます．
オイラー路においては頂点を2度以上使用してもいいはずです

自分がプログラムを読み切れていないだけかも知れないので，間違っていたら指摘をお願いします

[きっか]

回答ありがとうございます。
あれから、改良を加えてオイラー小路を求めることができました。
グラフ G （何も言わないときは無向グラフ）の小路 T は G のすべての辺を 通るとき、オイラー小路 （Euler trail ）と呼ばれる。 小路であるから、同じ辺は２度通らない、ひとつの頂点を 何度も訪れてもよい、ことに注意する。オイラー小路で閉じている（ 始点と終点が一致する）ものは当然ながら閉じたオイラー小路 と呼ばれる。グラフ G が連結でありかつ閉じたオイラー小路を持つとき、 G は オイラーグラフ と呼ばれる。
ということに、見落としていました。
解決しました。ありがとうございました。

[きっか]

回答ありがとうございます。
あれから、改良を加えてオイラー小路を求めることができました。
グラフ G （何も言わないときは無向グラフ）の小路 T は G のすべての辺を 通るとき、オイラー小路 （Euler trail ）と呼ばれる。 小路であるから、同じ辺は２度通らない、ひとつの頂点を 何度も訪れてもよい、ことに注意する。オイラー小路で閉じている（ 始点と終点が一致する）ものは当然ながら閉じたオイラー小路 と呼ばれる。グラフ G が連結でありかつ閉じたオイラー小路を持つとき、 G は オイラーグラフ と呼ばれる。
ということに、見落としていました。
解決しました。ありがとうございました。