プログラマ専用SNS ミクプラ

コード:

#include<stdio.h>
#define Node 4　　　/*Nodeを4に設定　接点の数*/
#define Root 6       /*Rootを6に設定　辺の数*/
#define Start 1      /*Startを1に設定　一筆書きの図の①から始めるということ*/

int a[Node+1][Node+1]={{0,0,0,0,0},
		　　　 {0,0,1,0,1},
		       {0,1,0,1,2},
   {0,0,1,0,1},
   {0,1,2,1,0}};
					   
int success,
	v[Root+1],
	n;

void visit(int);
	
void main(void)
	{
		success=0; n=Root;
		visit(Start);
		if(success==0) /*一度も始点に戻ってこれなかった場合*/
			printf("解なし\n");
	}

void visit(int i)
	{
		int j;
		v[n]=i;
		if(n==0 && i==Start){
			printf("解 %d:",++success);
			for(i=0;i<=Root;i++)
				printf("%d",v[i]);
			printf("\n");
		}
		else {
			for(j=1;j<=Node;j++)
				if(a[i][j]!=0){
					a[i][j]--;
					a[j][i]--;
					n--;
					visit(j);
					a[i][j]++;
					a[j][i]++;
					n++;
				}
	}
	}

コード:

#include <stdio.h>

#define NODE  4   /* NODEを 4に設定　節点の数 */
#define ROUTE 6   /* ROUTEを6に設定　辺の数   */
#define START 1   /* STARTを1に設定　点1から始める */
 
int a[NODE+1][NODE+1] = { /* a[i][j] は、点i から点j への辺の数 */
    { 0, 0, 0, 0, 0 }, 
    { 0, 0, 1, 0, 1 },  /* 点1から, 点2まで1本, 点4まで1本             */
    { 0, 1, 0, 1, 2 },  /* 点2から, 点1まで1本, 点3まで1本, 点4まで2本 */
    { 0, 0, 1, 0, 1 },  /* 点3から, 点2まで1本, 点4まで1本             */
    { 0, 1, 2, 1, 0 }   /* 点4から, 点1まで1本, 点2まで2本, 点3まで1本 */
};
                       
int success;      /* 見つかった経路の数 */
int v[ROUTE+1];   /* 経路(通過点の記録) */
int n;            /* 残りの辺の数       */
 
void visit(int);
    
int main(void)
{
    success = 0;       /* 経路が見つかっていない */
    n = ROUTE;         /* 開始前の残りの辺の数 */
    visit(START);      /* 探索開始 */
    if (success == 0)  /* 経路が一つも見つからなかった */
        printf("解なし\n");
    return 0;
}

void visit(int i)    /* 点i に行く */
{
    int j;
    v[n] = i;        /* 点i を経路に加える */
    if (n==0 && i==START) { /* 全部の辺を通って、始点に戻った */
        printf("解 %d:", ++success);
        for (i = 0; i <= ROUTE; i++)
            printf("%d", v[i]);
        printf("\n");
    }
    else {
        for (j = 1; j <= NODE; j++) {  /* 点j に行けるかどうか全部試す */
            if (a[i][j] != 0) {  /* 点i から点j への辺があった */
                a[i][j]--;   /* 点i から点j への辺を通るので減る */
                a[j][i]--;   /* 点j から点i への辺も減る */
                n--;         /* 残りの辺の数も減る */
                visit(j);    /* 点j に行く */
                a[i][j]++;   /* 点i から点j への辺復活 */
                a[j][i]++;   /* 点j から点i への辺復活 */
                n++;         /* 残りの辺の数も元の戻る */
            }
        }
    }
}