ショッピングモール  掲示板ランキング


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は謹んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.3259

グラフの探索について
投稿者---rina(2005/01/10 01:22:53)


環境
  OS    :WindowsXP
  コンパイラ:Microsoft Visual C++ version 6.0

深さ優先探索でグラフの探索プログラムを書いているのですが、今のところすべての頂点を探索するプログラムしか書けていません。
任意の頂点を入力し、その頂点を見付けた時点で探索をやめる、というプログラムを書きたいと思っていますが考えに詰まっています。何かいいアドバイスがあればお願いします。
下にソースを貼っておきます。少し手を加えれば出来そうな感じなのですが・・・。


#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<sys\timeb.h>
#include<conio.h>

#define N 20

int a[N+1] [N+1];
int S[N+1];


int v[N+1];

char *tzstr="TZ=JST-9";

void visit(int);

void main(void)
{
    struct timeb s,f;
double t;


    int i,j;

/*隣接行列Aと配列Sの初期化*/
    for(i=1;i<=N;++i)
    {
            S[i]=0;
            for(j=1;j<=N;++j)a[i][j]=-1;
    }

    /*辺の入力、隣接行列の作成;入力データの終了はi=-1で表す*/
    printf("辺(i,j)=");
    scanf("%d %d",&i,&j);
    while(i!=-1)
    {
        a[i][j]=1,a[j][i]=1;
        printf("辺(i,j)=");scanf("%d %d",&i,&j);
    }



    for(i=1;i<=N;i++)
        v[i]=0;
ftime(&s);


    visit(1);


ftime(&f);

t=(f.time+f.millitm*0.001)-(s.time+s.millitm*0.001); /*実行時間の計算*/

printf("\n\n実行時間は%f秒です。",t);

}



void visit(int i)

{
    int j;

    v[i]=1;
    for(j=1;j<=N;j++)
    {
        if(a[i][j]==1  &&  v[j]==0)
        {
            printf("%d->%d ",i,j);
                
            visit(j);

        }
       
    }
     
    
}







この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:グラフの探索について 3260 hh 2005/01/10 01:51:08
<子記事> Re:グラフの探索について 3261 あかま 2005/01/10 02:41:45


No.3260

Re:グラフの探索について
投稿者---hh(2005/01/10 01:51:08)


>任意の頂点を入力し、その頂点を見付けた時点で探索をやめる、というプログラムを書きたいと思っていますが考えに詰まっています。何かいいアドバイスがあればお願いします。

visitの中で頂点番号をチェックして、入力した頂点だったら探索をやめればいい
としかいいようがありません。
あなたが悩んでいるポイントをもっと「具体的に」書いて下さい。


この投稿にコメントする

削除パスワード

No.3261

Re:グラフの探索について
投稿者---あかま(2005/01/10 02:41:45)


>深さ優先探索でグラフの探索プログラムを書いているのですが、今のところすべての頂点を探索するプログラムしか書けていません。
>任意の頂点を入力し、その頂点を見付けた時点で探索をやめる、というプログラムを書きたいと思っていますが考えに詰まっています。何かいいアドバイスがあればお願いします。
入力例がないとこちらでプログラムを試せません。
もう少し具体的な出力例がないとアドバイスしづらいです。

>その頂点を見付けた時点で探索をやめる
これだけなら条件をif文で入れて見つかったらreturnするだけでしょう。
再帰関数なのでややこしいかもしれませんが、返り値あたりを使って戻った一つ上のvisit関数でも終了を判定しては?


この投稿にコメントする

削除パスワード

No.3262

Re:グラフの探索について
投稿者---hh(2005/01/10 02:57:51)


>再帰関数なのでややこしいかもしれませんが、返り値あたりを使って戻った一つ上のvisit関数でも終了を判定しては?

探索の時間打ち切り等で使用する一般的な方法ですが、終了用flagでも
用意して、必ずチェックする方が単純かもしれません。


この投稿にコメントする

削除パスワード

No.3263

Re:グラフの探索について
投稿者---rina(2005/01/10 03:30:05)


>入力例がないとこちらでプログラムを試せません。

1 2
1 8
1 12
1 15
2 4
2 6
3 5
3 9
4 6
4 15
4 20
5 9
5 11
6 8
6 18
6 19
7 10
8 16
9 20
10 15
11 19
12 13
13 16
13 17
14 15
15 19
-1 -1

の入力例(実行して貼り付ける)だと、
1->2 1->8 1->12 1->15 2->4 2->6 8->16 12->13 15->10 15->14 15->19 4->20 6->18 13
->17 10->7 19->11 20->9 11->5 9->3

実行時間は0.000000秒です。Press any key to continue
と出力されます。

データを入力した後に「頂点は?」等と出力し、そこに頂点の番号を入れるようにしたいと思っています。
その為に新たに変数を作った方がいいのでしょうか?
一番悩んでいる所はどういう条件式にするかです。解を見付けたら終了だと、言葉では表せるんですけど・・・。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity