グラフの隣接リストを表示させたい(深さ優先探索)(幅優先探索)

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
じゃみ
記事: 6
登録日時: 2年前

グラフの隣接リストを表示させたい(深さ優先探索)(幅優先探索)

#1

投稿記事 by じゃみ » 2年前

お気楽C言語プログラミング超入門
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;
}

よろしくお願いします。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: グラフの隣接リストを表示させたい(深さ優先探索)(幅優先探索)

#2

投稿記事 by みけCAT » 2年前

出力する行列の各行について、深さ優先探索をする時と同様に終端まで辺のリストを走査して、
辺がある場所をマークし、最後に行を出力するといいでしょう。

コード:

//隣接リスト
void printlist(void)
{
	for(int i = 1; i <= N; i++)
	{
		// 存在する辺をマークする
		int edges[N + 1] = {0};
		for(int j = 1; j < M; j++)
		{
			int y = a[i][j];
			if(y == 0) break;
			edges[y] = 1;
		}
		// 行を出力する
		printf("%d", edges[1]);
		for (int j = 2; j <= N; j++)
		{
			printf(" %d", edges[j]);
		}
		printf("\n");
	}
	printf("\n");
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

じゃみ
記事: 6
登録日時: 2年前

Re: グラフの隣接リストを表示させたい(深さ優先探索)(幅優先探索)

#3

投稿記事 by じゃみ » 2年前

>>みけCATさん
無事解決できました。
ありがとうございます。

返信

“C言語何でも質問掲示板” へ戻る