[C言語]経路探索

バックトラック: 失敗したら後戻りして別の道を選ぶ ->　メモリ使用量が少ない
幅優先探索: 全ての経路を並行して探索 ->　メモリ使用量が多い

隣接行列
N|ABCDEFG
A|0110000
B|1011000
C|1100100
D|0100110
E|0011001
F|0001000
G|0000100

int adjacent[N][N] {
	{0, 1, 1, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0},
	{1, 1, 0, 0, 1, 0, 0},
	{0, 1, 0, 0, 1, 1, 0},
	{0, 0, 1, 1, 0, 0, 1},
	{0, 0, 0, 1, 0, 0, 0},
	{0, 0, 0, 0, 1, 0, 0},
}

隣接リスト

enum {S, A, B, C, D, E, F, G};

int adjacent[N + 1][M] = {
	{S},
	{B, C, S},
	{A, C, D, S},
	{A, B, E, S},
	{B, E, F, S},
	{C, D, G, S},
	{D, S},
	{E, S},
};

### プログラム

#include 
#include  //  4 つのマクロが定義 bool, true, false, __bool_true_false_are_defined

#define N 7
#define M 4

enum {S, A, B, C, D, E, F, G};

int adjacent[N + 1][M] = {
	{S},
	{B, C, S},
	{A, C, D, S},
	{A, B, E, S},
	{B, E, F, S},
	{C, D, G, S},
	{D, S},
	{E, S},
};


// 経路
int path[N];
bool visited[N + 1];

// 経路の表示
void print_path(int n){
	for(int i = 0; i
$ ./main

A B C E G

A B D E G

A C B D E G

A C E G 
関数のdfsのint y = adjacent[x][i];で進んでいってるってこと？

A->B->C の順番の経路だから上のロジックでも成り立っているように見えるが。。。

それとvisitedの書き方がtrue -> 再帰処理 -> falseにする意味がよくわからん