ブログのネタがないので研究で使ったグラフ理論にける探索アルゴリズムでも紹介します。
プログラム組むの下手くそですがまぁ動作はするので......。
とりあえず幅優先探索とは何ぞやというところから説明しましょう。
まず元となるネットワークモデルは
こんな感じにしましょう。
さて実際に幅優先探索の動作ですキュー(queue)と呼ばれるデータ構造の一つを使います。
長くなるので興味がある人は下のMoreから続きを見てください〜。
プログラム組むの下手くそですがまぁ動作はするので......。
とりあえず幅優先探索とは何ぞやというところから説明しましょう。
まず元となるネットワークモデルは
こんな感じにしましょう。
さて実際に幅優先探索の動作ですキュー(queue)と呼ばれるデータ構造の一つを使います。
長くなるので興味がある人は下のMoreから続きを見てください〜。
図を使いながら説明しましょう。
まずキューに根っことなるノードを追加します。これが↑の図でいうノード番号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文で一緒に書けば出来るはずです。
まずキューに根っことなるノードを追加します。これが↑の図でいうノード番号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
プロフィール
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
最近は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
カレンダー
02 | 2024/03 | 04 |
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 |
カウンター
ブログ内検索
最新TB
フリーエリア
P R
アクセス解析
カウンター