掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

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

No.30240

無・有向グラフの経路
投稿者---ととろ(2007/05/30 22:45:41)


はじめて質問させていただくので、題名のつけ方がこれでよかったのかとか、
質問文に悪いところがあるのではないか、など不安な点はありますが
そういったマナーも含めてまずいところがあれば御指摘お願いいたします。

ここからが質問なのですが、
;;、◆    a────b
|  / |     |     / |
| / |     |   /  |
↓/  ↓     | /    |
←──ぁ    c────d

ちなみに左の図は、UNICODE文字が使えなかったので斜め矢印を書いていませんが、
から△妨けて矢印があります。

上図(左)のような有向グラフがあり、経路の長さが3になるような(つまり矢印を3回たどる)
経路を全て書き出しなさい、といった問題を出されたのですが、
普通にひとつひとつ手書きで書き出していくのは何の問題もないので
提出課題はそれで提出できるのですが、同じ作業をコンピュータにやらせてみようと
思ってプログラムを組んでいるのですが、行き詰ったのでヒントがほしいです。
何が行き詰っているのかというと、先の例のグラフは有向グラフでしたが
同じ道が繋がれているけれども無向グラフである場合に、
つまり上図(右)のような時に全ての道順としてたとえば、
a→b b→c c→d
a→b b→c c→a
の例のように途中まで同じ経路で最後で枝分かれしているような状態の経路まで
全部走査できるようなプログラムにするにはどうすればいいのかわからなくなっているということです。

■ソースコード(有向グラフの例)
(コメント書いてなくてすいません。)

#include <stdio.h>

#define KEIRO   3

int cnt = 0;

int graph_v[4][4] = { {0, 1, 1, 0},
                    {0, 0, 0, 1},
                    {0, 1, 0, 0},
                    {0, 0, 1, 0}
};

void disp(int x, int y)
{
    char str1, str2;
    
    switch(x) {
        case 0: str1 = 'a';break;
        case 1: str1 = 'b';break;
        case 2: str1 = 'c';break;
        case 3: str1 = 'd';break;
    }
    switch(y) {
        case 0: str2 = 'a';break;
        case 1: str2 = 'b';break;
        case 2: str2 = 'c';break;
        case 3: str2 = 'd';break;
    }
    
    printf("%c → %c ", str1, str2);
}

void keiro(int st)
{
    int end;
    
    for(end=0; end<4; end++) {
        if(graph_v[st][end] == 1 && cnt != KEIRO) {
            cnt++;
            disp(st, end);
            keiro(end);
        }
    }
}

void main(void)
{
    int i;
    for(i=0; i<4; i++) {
        keiro(i);
        putchar('\n');
        cnt = 0;
    }
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:無・有向グラフの経路 30245 ぽへぇ 2007/05/31 06:06:42
<子記事> Re:無・有向グラフの経路 30249 TT414 2007/05/31 11:04:13
<子記事> Re:無・有向グラフの経路 30251 acid 2007/05/31 12:43:11
<子記事> Re:無・有向グラフの経路 30254 rvr_driver 2007/05/31 15:49:59


No.30245

Re:無・有向グラフの経路
投稿者---ぽへぇ(2007/05/31 06:06:42)


>a→b b→c c→a
>の例のように途中まで同じ経路で最後で
>枝分かれしているような状態の経路まで

a→b b→a a→b というのも経路に含めますか?



この投稿にコメントする

削除パスワード

No.30258

Re:無・有向グラフの経路
投稿者---ととろ(2007/05/31 16:52:04)


>a→b b→a a→b というのも経路に含めますか?
すいません。補足忘れです。
一度通った頂点へは、終点として2回行く場合を除いて、重複して通ってはいけないという条件付きでした。


この投稿にコメントする

削除パスワード

No.30249

Re:無・有向グラフの経路
投稿者---TT414(2007/05/31 11:04:13)


>そういったマナーも含めてまずいところがあれば御指摘お願いいたします。

>;;、◆    a────b
>←──ぁ    c────d

丸数字は、「機種依存文字」、「OS依存文字」、「フォント依存文字」などと云われる文字です。

使用しないようにしましょう。


この投稿にコメントする

削除パスワード

No.30259

Re:無・有向グラフの経路
投稿者---ととろ(2007/05/31 16:55:34)


>丸数字は、「機種依存文字」、「OS依存文字」、「フォント依存文字」などと云われる文字です。
>使用しないようにしましょう。
やはりそうでしたか。次回から気を付けます。
ありがとうございます。


この投稿にコメントする

削除パスワード

No.30251

Re:無・有向グラフの経路
投稿者---acid(2007/05/31 12:43:11)



配列の定義はどうなっていますか?
0が不通で、1が通行可能でいいのでしょうか。

{0, 1, 1, 0},
これは、bとcにつながってる?

あとグローバル変数使うなら、頭にg_とかつけてください。
もちろん使わないにこしたことはありませんが。



この投稿にコメントする

削除パスワード

No.30255

Re:無・有向グラフの経路
投稿者---TMC(2007/05/31 16:02:53)


>あとグローバル変数使うなら、頭にg_とかつけてください。

そこは別に指摘するところじゃないと思うけど。
どちらかというと、本筋が分からないから適当なところを指摘しているだけにしか見えません。



この投稿にコメントする

削除パスワード

No.30257

Re:無・有向グラフの経路
投稿者---ととろ(2007/05/31 16:48:43)


>配列の定義はどうなっていますか?
>0が不通で、1が通行可能でいいのでしょうか。
>{0, 1, 1, 0},
>これは、bとcにつながってる?
補足してなくてすいませんでした。そのとおりです。

>あとグローバル変数使うなら、頭にg_とかつけてください。
>もちろん使わないにこしたことはありませんが。
大きいプログラムでグローバル変数を使う時には把握しきれなくなるので
そのようにg_と付けた方がわかりやすそうですね。
参考にさせていただきます。


この投稿にコメントする

削除パスワード

No.30264

Re:無・有向グラフの経路
投稿者---rvr_driver(2007/06/01 07:17:38)


>大きいプログラムでグローバル変数を使う時には把握しきれなくなるので
>そのようにg_と付けた方がわかりやすそうですね。
>参考にさせていただきます。

コーディング規約がない環境で適当に名前をつけている場合は下記を参考にしてみては?
勿論コーディング規約がある場合はそれに従うこと。

「プログラミング作法」(著者:Brian W.Kernighan、RobPik)の「1.1名前」から引用

「グローバルにはわかりやすい名前を、ローカルには短い名前を。グローバル変数は
 その定義上プログラムのどこにでもひょっこり出現する可能性があるので、読む人
 がその意味を思い出せる程度に長く、説明的な名前をつけておくのも役に立つ。

  int npending = 0; // 現在のキューの長さ

  グローバルな関数とクラスと構造体にも、プログラムの中での役割を表す説明的な
 名前をつける必要がある。
  それとは逆に、ローカル変数には短めの名前で十分だ。関数の内部でならおそら
 くnで十分だし、npointsなら申し分ないし、numberOfPointsだとやりすぎだ。
  特定の場面で使われるローカル変数はごく短い名前でかまわない。ループインデッ
 クスのiとj、ポインタのpとq、文字列のsとtは非常に多く使われるので、こ
 れより長い名前を使ってもあまりメリットはないし、おそらく無駄だろうと思う。」



この投稿にコメントする

削除パスワード

No.30254

Re:無・有向グラフの経路
投稿者---rvr_driver(2007/05/31 15:49:59)


こんな感じでよろしいのでしょうか?

変更した点は
・graph_vの設定変更
・keiro()の仕様変更
です。

keiro()の中でcntを変更していることが問題のようです。

# 再帰に関して私も良くわからないので識者の方
# のコメントがあると嬉しいです。

#include <stdio.h>

#define NODE_NUM    4
#define KEIRO      3

int graph_v[NODE_NUM][NODE_NUM] = { {0, 1, 1, 0},
                                    {1, 0, 1, 1},
                                    {1, 1, 0, 1},
                                    {0, 1, 1, 0}
};

void disp(int x, int y)
{
    char str1, str2;
    
    switch(x) {
        case 0: str1 = 'a';break;
        case 1: str1 = 'b';break;
        case 2: str1 = 'c';break;
        case 3: str1 = 'd';break;
    }
    switch(y) {
        case 0: str2 = 'a';break;
        case 1: str2 = 'b';break;
        case 2: str2 = 'c';break;
        case 3: str2 = 'd';break;
    }
    
    printf("%c → %c\n", str1, str2);
}

void keiro(int st, int num)
{
    int end;

    if (!num) {
        return ;
    }

    for(end=0; end<NODE_NUM; end++) {
        if(graph_v[st][end] == 1) {
            if (num == 1) {
                printf("              ");
            } else if (num == 2) {
                printf("       ");
            }

            disp(st, end);
            keiro(end, num - 1);
        }
    }
}

void main(void)
{
    int i;
    for(i=0; i<NODE_NUM; i++) {
        keiro(i, KEIRO);
        putchar('\n');
    }
}




この投稿にコメントする

削除パスワード

No.30260

Re:無・有向グラフの経路
投稿者---ととろ(2007/05/31 17:14:32)


お忙しいところコードまで書いていただいてありがとうございます。
これで最初に質問させていただいた条件を満たすプログラムになりました。

ですが、ぽへぇさんの方にもレスさせていただいたのですが、
最初の質問に条件を書き忘れていたため、未だ全ての条件を満たすものになっておりません。
とりあえずここで再度その条件を載せておきます。
<条件>
一度通った頂点へは、終点として2回行く場合を除いて、重複して通ってはいけない。

そこでその条件を加えて書きなおすとすると、今回の場合に限っては
#define KEIRO 3
なので再帰的に1回目に呼び出す時の元の頂点がどこであったかを
覚えておけばいいと思うのですが、
([例] a→b b→c c→dという経路の場合は最初の頂点a)
それを新たな変数に記録しておくとして、その後どのように使えばいいのかがわからないです。
それか、他に何かいいアイディアがあればそちらでも構いませんので、お教えいただけないでしょうか。


この投稿にコメントする

削除パスワード

No.30261

Re:無・有向グラフの経路
投稿者---rvr_driver(2007/05/31 17:42:01)


>なので再帰的に1回目に呼び出す時の元の頂点がどこであったかを
>覚えておけばいいと思うのですが、
>([例] a→b b→c c→dという経路の場合は最初の頂点a)
>それを新たな変数に記録しておくとして、その後どのように使えばいいのかがわからないです。

方向性がある程度見えているのであれば、試してみてはいかがでしょうか?
その結果判らないところがあればここで質問をする、というスタンスを
とれば皆さんからのアドバイスをいただけると思います。


この投稿にコメントする

削除パスワード

No.30262

Re:無・有向グラフの経路
投稿者---ととろ(2007/05/31 18:29:42)


すいません、とりあえず先に、前のレスで<条件>を書きましたが、
条件にツメの甘さがあったので補足です。

<条件(補足版)>
一度とおった道は重複してとおってはいけない。

これでシンプルで意味の通る条件となりました。

>方向性がある程度見えているのであれば、試してみてはいかがでしょうか?
>その結果判らないところがあればここで質問をする、というスタンスを
>とれば皆さんからのアドバイスをいただけると思います。
ということですが、自分のアイディアで進めていこうと思ったのですが、
最初のスタート地点だけを記録しておくだけでは
a→b b→c c→bという経路を排除する事はできなさそうなので、
経由した頂点すべてを憶えておいて、そこへ戻らないようにしなければならないということになりました。
ということで考えましたが、アイディアに行き詰っております。
よろしければ少しヒントを与えていただけないでしょうか?


この投稿にコメントする

削除パスワード

No.30263

Re:無・有向グラフの経路
投稿者---rvr_driver(2007/05/31 19:08:15)


>a→b b→c c→bという経路を排除する事はできなさそうなので、
>経由した頂点すべてを憶えておいて、そこへ戻らないようにしなければならないということになりました。

個人的にはその考え方で問題ないと思います。
あとは実装だけですね。

進め方)
私が投稿したソースはすべてのパターンが表示されるので
それを基にして進める方法を書いておきます。
1.経由した頂点を記憶させるコードを書く。
2.disp()で経路表示をした後に今まで経由した頂点を表示してみる。
3.経由した頂点が表示されなかったら1へ戻る。
  経由した頂点が表示されたら4へ。
4.表示する経路を希望する条件に設定し表示してみる。
5.希望する表示が得られなかったら4へ。


この投稿にコメントする

削除パスワード

No.30272

Re:無・有向グラフの経路
投稿者---ととろ(2007/06/03 23:11:03)


返事が遅くなり申し訳在りません。

とりあえず自分で考えたやり方でプログラムを書いてみたらうまくいきました。
やり方をまとめると、ユーザ関数keiro()に、呼び出す一個手前の時の頂点の値を呼び出し時に渡して、その値を利用してもとの頂点に戻ってしまわないようにしました。
これで解決といたします。
教えていただいたみなさまありがとうございました。

以下がそのソースコードになります。

#include <stdio.h>

#define NODE_NUM    4
#define KEIRO      3

int graph_v[NODE_NUM][NODE_NUM] = { {0, 1, 1, 0},
                                    {1, 0, 1, 1},
                                    {1, 1, 0, 1},
                                    {0, 1, 1, 0}
};

void disp(int x, int y)
{
    char str1, str2;
    
    switch(x) {
        case 0: str1 = 'a';break;
        case 1: str1 = 'b';break;
        case 2: str1 = 'c';break;
        case 3: str1 = 'd';break;
    }
    switch(y) {
        case 0: str2 = 'a';break;
        case 1: str2 = 'b';break;
        case 2: str2 = 'c';break;
        case 3: str2 = 'd';break;
    }
    
    printf("%c → %c\n", str1, str2);
}

void keiro(int st, int num, int chk)
{
    int end;

    if (!num) {
        return ;
    }

    for(end=0; end<NODE_NUM; end++) {
        if(chk != end) {
            if(graph_v[st][end] == 1) {
                if (num == 1) {
                    printf("              ");
                } else if (num == 2) {
                    printf("       ");
                }
    
                disp(st, end);
                keiro(end, num - 1, st);
            }
        }
    }
}

void main(void)
{
    int i;
    for(i=0; i<NODE_NUM; i++) {
        keiro(i, KEIRO, 5); // 5は0〜3以外の適当な値);
        putchar('\n');
    }
}



この投稿にコメントする

削除パスワード

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