再帰関数を利用した深さ優先探索関数DFSの実装について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 再帰関数を利用した深さ優先探索関数DFSの実装について

Re: 再帰関数を利用した深さ優先探索関数DFSの実装について

#3

by snr » 7年前

回答ありがとうございます

図を描いて、動作することを確認しました。
自分には難解ですが時間をかけてみようと思います

Re: 再帰関数を利用した深さ優先探索関数DFSの実装について

#2

by かずま » 7年前

グラフなら探索済み変数が必要かもしれませんが、
木構造なら不要だと思います。

コード: 

#include <stdio.h>

typedef struct _treenode {
	int data;
	struct _treenode *left;
	struct _treenode *right;
} Tree;

Tree *dfs(Tree *node, long data)
{
	Tree *p;
	if (node->data == data) return node;
	if (node->left && (p = dfs(node->left, data))) return p;
	if (node->right && (p = dfs(node->right, data))) return p;
	return NULL;
}

Tree root[] = {
	{ 1, root+1, root+3 },
	{ 2, root+2, NULL },
	{ 3, root+4, root+5 },
	{ 4, NULL, NULL },
	{ 5, NULL, NULL },
	{ 6, NULL, NULL },
};

int main(void)
{
	int data = 5;
	Tree *p = dfs(root, data);
	if (p)
		printf("%d found\n", p->data);
	else
		printf("%d not found\n", data);
}
root[] は自分で図を書いてみてくださいね。

再帰関数を利用した深さ優先探索関数DFSの実装について

#1

by snr » 7年前

木構造を深さ優先探索する関数DFSの作成を目標にしています

コード: 

typedef struct _treenode{
	int data;
	struct _treenode *left;
	struct _treenode *right;
}Tree;
以上が木のデータ構造です。

これを再帰関数を使って深さ優先探索を実装したいのですが、
関数の定義は引数に制約があるため自作できません。
どうかご教授お願いいたします。

以下が関数とその引数です。
呼び出し時に木の根を引数にし、dataに探索するデータを入れることで、
データと一致するノードを返すという関数です。

コード: 

Tree *dfs(Tree *node ,long data)

ネットで調べたのですが、やはり探索済みかどうかを記録したり
など変数を作っていましたが、それは今回の制約の外で
実際、そういった変数は必要なく、コールスタックを利用することで
作れるそうです。

ページトップ