http://www.nct9.ne.jp/m_hiroi/linux/clang16.html
↑のサイトを参考に、あるグラフを深さ優先探索で辿るコードを書きました。
下記の「//隣接リスト」の部分を付け加えたのですが、うまく隣接リストが表示できません。
隣接リストを文字(あるいは数値でもいいのですが)の行列のような形で表示させる方法を教えていただきたいです。
#include <stdio.h>
#include <stdbool.h>
enum {S, A, B, C, D, E, F, G}; //Sは終端を表す
#define N 7
#define M 4
// 隣接リスト
int a[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},
};
//隣接リスト
void printlist(void)
{
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
printf("\n");
}
// 経路
int path[N];
bool visited[N + 1];
// 経路の表示
void print_path(int n)
{
for(int i = 0; i < n; i++)
{
printf("%c ", 'A' + path[i] - 1);
}
printf("\n");
}
// 深さ優先探索
void dfs(int n, int goal)
{
int x = path[n - 1];
if(x == goal)
{
print_path(n);
}
else
{
for(int i = 0; i < M; i++)
{
int y = a[x][i];
if(y == 0) break;
if(!visited[y])
{
path[n] = y;
visited[y] = true;
dfs(n + 1, goal);
visited[y] = false;
}
}
}
}
int main(void)
{
printlist();
path[0] = A;
visited[A] = true;
dfs(1, G);
return 0;
}