前提・実現したいこと
隣接行列と再帰関数を使って深さ優先探索を行う
発生している問題・エラーメッセージ
processingでの再帰関数の使い方がわかりません
該当のソースコード
processing
1void setup(){ 2} 3void draw(){ 4 print(search((n-1))); 5} 6int [][] N={ 7 {0,1,1,0,0,0,0,0,0,0}, 8 {1,0,0,1,1,0,0,0,0,0}, 9 {1,0,0,0,0,1,1,0,0,0}, 10 {0,1,0,0,0,0,0,0,0,0}, 11 {0,1,0,0,0,0,0,1,1,0}, 12 {0,0,1,0,0,0,0,0,0,0}, 13 {0,0,1,0,0,0,0,0,0,1}, 14 {0,0,0,0,1,0,0,0,0,0}, 15 {0,0,0,0,1,0,0,0,0,0}, 16 {0,0,0,0,0,0,1,0,0,0}}; 17int n=10; 18int []a={0,0,0,0,0,0,0,0,0,0}; 19int search(int i){ 20 int j; 21 a[i]=1; 22 for(j=0;j<n;j++){ 23 if(N[i][j]==1&&a[j]==0){ 24 return search(j); 25 }else if(N[i][j]==1&&a[i]==0&&a[j]==1){ 26 a[i]=2; 27 return search(j); 28 } 29 } 30 if(i==0){ 31 noLoop(); 32 } 33 return i; 34}
試したこと
隣接行列の行と列を入れ替えて探索するように書いてみたが、途中で無限ループして諦めました。
補足情報(FW/ツールのバージョンなど)
無限ループするもので構わないので、ソースコードを貼ってくれないとアドバイスのしようがありません。
ごめんなさい‼
コードは以下の感じで書きました。
void setup(){
}
void draw(){
print(search((n-1)));
}
int [][] N={
{0,1,1,0,0,0,0,0,0,0},
{1,0,0,1,1,0,0,0,0,0},
{1,0,0,0,0,1,1,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,1,1,0},
{0,0,1,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,1},
{0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,1,0,0,0}};
int n=10;
int a,b;
int search(int i){
int j;
for(j=0;j<n;j++){
if(N[i][j]==1&&i<j){
a=i;
b=j;
i=j;
}else if(N[i][j]==1&&i>j){
i=a;
j=b;
}
}
return i;
}
探索済みかどうかを覚えておくフラグの配列が必要なのでは。
他の言語で書かれたものも参考に見たのですが、探索済みのものをtrueとしてtrueは探索しないようにするイメージはわかるのですが書き方がわからない感じです。
コードはインデントが失われないように <code> 機能を使って貼ってくれると嬉しいです。
https://orenodiy.com/teratail-question-howto#toc8
そして、よく見ると再帰になってない (search の中で search を呼んでない) ですし、無限ループに見えるのは Processing が毎フレーム draw を呼んでいるだけですね。
関数の目的ですが、例えば i = n - 1 = 9 から始めて、最終的に何を返したい (または出力したい) のでしょうか?
目的は深さ優先探索において、それ以上探索できなくなった場合でiを出力し、どの順番で探索されたかを調べる感じです。
例えば、0-1
-2みたいな感じだったら、1,2,0という順番で表示させる感じです。
回答1件
あなたの回答
tips
プレビュー