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

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

ただいまの
回答率

87.59%

C言語 深さ優先探索について

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 1,676

score 12

C言語での深さ優先探索の実装についての質問です。

下に添付してあるのは幅優先探索のコードです。
このコードを元に深さ優先探索を実装したいのですが、どのように実装すればようでしょうか。

わかる方、教えてください。

また、木構造のTextデータは下のとおりです。

1
 2
  3
  4
 5
  6
#include <stdio.h>
#include <stdlib.h>

#define BUFSIZE 256

struct node{
  int value;
  struct node *left;
  struct node *right;
};

int search_breadth1(int key, struct node *remain[]){
  int idx = 0;
  int last = 1;

  while(remain[idx] != NULL){
    if(remain[idx]->value == key){
      return 1;
    }else{
      if(remain[idx]->left != NULL){ remain[last++] = remain[idx]->left; }
      if(remain[idx]->right != NULL){ remain[last++] = remain[idx]->right; }
      idx++;
    }
  }

  return 0;
}

int search_breadth(struct node *root, int key){
  struct node *remain[BUFSIZE];
  int i;

  remain[0] = root;
  for(i = 1; i < BUFSIZE; i++){ remain[i] = NULL; }

  return search_breadth1(key, remain);
}

struct node *addnode(struct node *root, int depth, int val){
  struct node *n, *new;

  new = (struct node *)malloc(sizeof(struct node));
  new->value = val;
  new->left = new->right = NULL;

  if(root == NULL){
    return new;
  }else{
    n = root;
  }

  for( ; depth > 1; depth--){
    if(n->right != NULL){
      n = n->right;
    }else if(n->left != NULL){
      n = n->left;
    }else{
      return NULL;
    }
  }

  if(n->left == NULL){
    n->left = new;
  }else if(n->right == NULL){
    n->right = new;
  }else{
    return NULL;
  }

  return root;
}

struct node *loaddata(char *filename){
  int depth, val;
  FILE *input;
  struct node *root = NULL;
  char line[BUFSIZE];

  input = fopen(filename, "r");
  if(input == NULL){
    fprintf(stderr, "Can't open file: %s\n", filename);
    exit(1);
  }

  while(fgets(line, sizeof(line), input) != NULL){
    depth = 0;
    while(line[depth] == ' '){
      depth++;
    }

    sscanf(&line[depth], "%d", &val);
    root = addnode(root, depth, val);
    if(root == NULL){
      fprintf(stderr, "illegal input file: %s\n", line);
      exit(1);
    }
  }

  fclose(input);

  return root;
}

int main(int ac, char **av){
  int result;
  struct node *root;

  if(ac != 3){
    fprintf(stderr, "Usage: %s <datafile> <key>\n", av[0]);
    exit(1);
  }

  root = loaddata(av[1]);

  result = search_breadth(root, atoi(av[2]));

  printf("Key \"%s\" is %s.\n", av[2], result == 1 ? "found" : "not found");

  return 0;
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

0

ソースが長いの、代わりにかいつまんで書くと、
深さ優先とは、

1
   2
      3
      4
   5
      6


で、1-2->と進み、3->4 を検査します。3も4も失敗の時は、5に戻って6に進みます。
広さ優先であれば、
1->2->5->3->4->6 という順序で進みます。
else 
```

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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