忍者ブログ
写真のこととかをメインで書こうかなと思っているのです。
[10]  [9]  [8]  [7]  [6]  [5]  [4]  [3]  [2]  [1
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

ブログのネタがないので研究で使ったグラフ理論にける探索アルゴリズムでも紹介します。
プログラム組むの下手くそですがまぁ動作はするので......。

とりあえず幅優先探索とは何ぞやというところから説明しましょう。
まず元となるネットワークモデルは
1b7a55b7.jpg







こんな感じにしましょう。

さて実際に幅優先探索の動作ですキュー(queue)と呼ばれるデータ構造の一つを使います。
長くなるので興味がある人は下のMoreから続きを見てください〜。
 

図を使いながら説明しましょう。

3852613a.jpg









まずキューに根っことなるノードを追加します。これが↑の図でいうノード番号0です。
次にキューからノードを取り出し子があれば追加します。それをキューが空になるまで行います。

まぁ文章能力が低いので伝わりにくいかもしれませんが始点を追加してそこから隣接しているノードを追加する処理を空になるまで永遠行うということです。

ということで実際にプログラムで実装してみましょう。


言語はC++で分割コンパイルにて処理を行います。
”bfs.h”
#pragma once

#include <iostream>
#include <stack>
#include <queue>

enum{PEER_SIZE = 8};

using namespace std;

class Bfs
{
private:
    int flag[PEER_SIZE + 1];      //ここはbool型でflag =  true or falseの処理でもおkです

    queue<int> bfs_queue;

public:
    Bfs(void);
    ~Bfs(void);

    void FormatData(void); //フラグの初期化用

    void BreadthFirstSearch(const int all_peer); //幅優先探索

};

"bfs.cpp"
#include <iostream>
#include <stack>
#include <queue>

#include "bfs.h"

using namespace std;

Bfs::Bfs(void)
{
}

Bfs::~Bfs(void)
{
}

void Bfs::FormatData(void)
{
    for(unsigned int i = 0;i < PEER_SIZE + 1; i++){
        flag[i] = 0;
    }
}

void Bfs::BreadthFirstSearch(const int all_peer)
{
    FormatData();
    int ConnectionInf[PEER_SIZE+1][PEER_SIZE+1] = {//隣接情報格納、0=隣接でない、1=隣接、2=同値
        {2, 1, 0, 1, 0, 0, 0, 0, 0},
        {1, 2, 1, 0, 0, 0, 1, 1, 0},
        {0, 1, 2, 1, 1, 0, 1, 0, 0},
        {1, 0, 1, 2, 1, 0, 0, 0, 0},
        {0, 0, 1, 1, 2, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 2, 1, 0, 1},
        {0, 1, 1, 0, 0, 1, 2, 1, 1},
        {0, 1, 0, 0, 0, 0, 1, 2, 0},
        {0, 0, 0, 0, 1, 1, 1, 0, 2},
    };

    bfs_queue.push(all_peer); //根の追加
    flag[all_peer] = 1;    //根のピアにはflagをたてる
    while(!bfs_queue.empty()){   //キューが空でない限りループ
        int i = bfs_queue.front(); //キューの先頭の要素
        bfs_queue.pop(); //キューから取り出す
        for(unsigned int j = 1;j < PEER_SIZE + 1; j++){
            if(ConnectionInf[i][j] == 1 && flag[j] == 0){  //隣接かつフラグが立っていないピアならば
                flag[j] = 1; //フラグを立てる
                bfs_queue.push(j); //キューに追加する
                cout << i << "->" << j << " " << endl;
            }
        }
    }
}

"main.cpp"
#include <iostream>

#include "bfs.h"

using namespace std;

class Bfs;

void main()
{
   Bfs fs;

    fs.BreadthFirstSearch(0);

    return;

}

出力結果
0->1
0->3
1->2
1->6
1->7
3->4
6->5
6->8

図の通りになってますね。
こんな感じで幅優先探索は実装できます。分割コンパイラで作らないのです~って人余計なクラス情報を消してmain文で一緒に書けば出来るはずです。
 
PR
back
COMMENT
name
title
text
color   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
mail
URL
pass
secret
無題
なるほど、わからん。
写カツ 2012/01/22(Sun)23:39:18 編集
無題
>>写カツ
俺も最初全く意味わからなかったわw
わっちっち 2012/01/23(Mon)01:24:56 編集
TRACKBACK
TrackbackURL:
PREV ←  HOME  → NEXT
プロフィール
HN:
わっちっち
性別:
男性
職業:
NE
趣味:
写真
自己紹介:
マンガとか本読んだりするのが好きなのです。
最近はsonyの一眼α65を購入して写真を撮ったりしていることのほうが多いです。この間日産のティーダラティオを購入したので色々なところへ写真を取りに行くのです。

PC環境
・デスクトップ
Win7 64bit,Core i5-650 3.20GHz,4G,GF PGTS450/1GD5,600W
・Macbook
Max OS 10.6 Snow Leopard,Core 2 Duo 2.4GHz,4G DDR3,GF 320M

デバイス
・マウス/Microsoft IE3.0
・キーボード/Razer BlackWidow
・マウスパッド/SteelSeries QcK mini 63005
・ディスプレイ/DELL初期24inch wide
・ヘッドセット/CyberSnipe Sonar 5.1 Championship Headset
カレンダー
11 2017/12 01
S M T W T F S
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
カウンター
ブログ内検索
最新CM
[12/16 わっちっち]
[12/07 写カツ]
[09/12 わっちっち]
[09/12 わっちっち]
[09/10 ねぎこーら]
最新TB
最古記事
バーコード
フリーエリア
P R
アクセス解析
カウンター
Copyright (C) 2017 楽園のわっちぶろぐ All Rights Reserved.

Photo by (c)Tomo.Yun   TemplateDesign by kaie
忍者ブログ [PR]