質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.77%

探索のアルゴリズムについて

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 687

score 16

探索のアルゴリズムを書いたのですが間違っているようです。

スタックとキューの使い方についてアドバイスいただけませんか

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 8

void print_matrix(int a[][N]);

int main(void){

  int stack[N],Adjacency_matrix[N][N],visit[N];
  int top,i,j,count_l,k;

  /*-------------------------------------------------------------------*/
  //隣接行列の作成

 srand(time(NULL));

  for(i=0;i<8;i++){
    for(j=0;j<8;j++){

      Adjacency_matrix[i][j] = rand() % 2;
      //printf("%d\n",Adjacency_matrix[i][j]);
      if(i == j){
    Adjacency_matrix[i][j] = 0;
      }
    }
    //sleep(1);
  }

  //行列の表示
  print_matrix(Adjacency_matrix);
  /*------------------------------------------------------------------*/
  //深さ優先探索開始。。。。
  printf("-------------------------深さ優先探索------------------------\n");

  //配列の初期化
  for(i=0;i<8;i++){ 

    visit[i] = 0; stack[i] = 0;
}

  //topと出発点を定める。。。。。 
  top = 0;   stack[top] = 0;   top++;
  printf("出発点は0です →");

  //出発点を訪問済みと定義
  visit[0] = 1;

  for(k=0;k<8;k++){

      for(i=0;i<8;i++){

      if(Adjacency_matrix[0][i] == 1 && visit[i] == 0){

      stack[top] = i;top++;visit[i] += 1;
      printf("%d→",stack[top - 1]);

      for(j=0;j<8;j++){

    if(Adjacency_matrix[i][j] == 1 && visit[j] == 0){

        stack[top] = j;top++; visit[j] += 1;
            printf("%d→",stack[top - 1]);


            break;
    }

        top--; stack[top] = -1;
    } 
  }
     }

        top = 0;

        for(i=0;i<8;i++){
          if(visit[i] == 0){
        stack[top] = i;top++;
                visit[i] = 1;
                printf("終了\n");
        printf("出発点は%d→",i);
        break; }

        if(i == 7)break;
  }
  }
  printf("終了\n");
      /*-----------------------------------------------------------*/         
//幅優先探索
 printf("-------------------------幅優先探索-------------------------\n");

  int queue[N];
  int first,last;

  first = 0; last = 0;

    for(i=0;i<8;i++){ 

    visit[i] = 0; queue[i] = 0;
}

  //出発点を定める。。。。。 
  printf("出発点は0です →");

  //出発点を訪問済みと定義
  visit[0] = 1;

  for(k=0;k<8;k++){
    for(i=0;i<8;i++){

      if(Adjacency_matrix[queue[first % N]][i] == 1 && visit[i] == 0){

    queue[last] = i; last = (last + 1) % 8; visit[i] += 1;
    printf("%d→",i);     
      }

      if(i == 7){
    queue[first] = -1; first =  (first + 1) % 8;
      }


    }    

    first = 0; last = 0;

        for(i=0;i<8;i++){
          if(visit[i] == 0){
        queue[last] = i;last++;
                visit[i] = 1;
                printf("終了\n");
        printf("出発点は%d→",i);
        break; }

        if(i == 7)break;

  }

        /* printf("\n");
    for(i = 0;i < 8;i++){
      printf(" %d ",visit[i]);
    }
    printf("\n");
        */


  }

  printf("終了\n");

  }

//行列を表示する関数
void print_matrix(int a[][N]) 
{
  int i, j;

  for(i=0;i<N;i++) {
    for(j=0;j<N;j++){ 
      printf("%d ", a[i][j]);}
    printf("\n");
  }
  return;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • nob.

    2019/01/16 11:05

    「ソースを読んで考えてくれ」、じゃあんまりです。
    どういう結果を欲しくて、どう考えてこのコードを書いたのか。
    実際の動きは期待とどう異なっていたのか。
    どういう方針で、どこまで調べたのか。
    こういった点について、質問に追記してください。

    キャンセル

  • episteme

    2019/01/16 20:10

    質問の体裁を成していない。やりなおし。

    キャンセル

  • 退会済みユーザー

    2019/01/17 15:45

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 1

checkベストアンサー

+2

http://flute.u-shizuoka-ken.ac.jp/~s-okubo/class/language/t006.htm

スタックとキューの解説ならここを参考にすると良いでしょう。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.77%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る