@blog.justoneplanet.info

日々勉強

iPhoneでHello Worldする

Xcodeをつかうよ((o(^-^)o))ワクワク

■初期設定

「起動 > 新規Xcodeプロジェクトを作成 > iOS > Application > Window-based Application」を選択する。

この時、iPhone、iPad、Universal(両方)が選択できる。また、テンプレートについては以下のようになっている。

最後に、プロジェクトの名前を入力して保存を押す。

■コード

HelloWorld/Classes/HelloWorldAppDelegate.h

#import <UIKit/UIKit.h>

@interface HelloWorldAppDelegate : NSObject <UIApplicationDelegate> {
    UIWindow *_window;
}
@property (nonatomic, retain) IBOutlet UIWindow *window;
@end

HelloWorld/Classes/HelloWorldAppDelegate.m

#import "HelloWorldAppDelegate.h"
#import "HelloWorld.h"

@implementation HelloWorldAppDelegate
@synthesize window = _window;
#pragma mark -
#pragma mark Application lifecycle
- (BOOL)application:(UIApplication *)application didFinishLaunchingWithOptions:(NSDictionary *)launchOptions {    
    // Override point for customization after application launch.
    UIView *view = [[HelloWorld alloc] initWithFrame:CGRectMake(0, 20, 320, 460)];
    [_window addSubview:view];
    [view release];
    [_window makeKeyAndVisible];
    return YES;
}
- (void)applicationWillResignActive:(UIApplication *)application {
}
- (void)applicationDidEnterBackground:(UIApplication *)application {
}
- (void)applicationWillEnterForeground:(UIApplication *)application {
}
- (void)applicationDidBecomeActive:(UIApplication *)application {
}
- (void)applicationWillTerminate:(UIApplication *)application {
}
#pragma mark -
#pragma mark Memory management
- (void)applicationDidReceiveMemoryWarning:(UIApplication *)application {
}
- (void)dealloc {
    [_window release];
    [super dealloc];
}
@end

HelloWorld/HelloWorld.h

#import <UIKit/UIKit.h>

@interface HelloWorld : UIView {
}
@end

HelloWorld/HelloWorld.m

#import "HelloWorld.h"

@implementation HelloWorld
-(id)initWithFrame:(CGRect)frame {
	if(self=[super initWithFrame:frame]){
		self.backgroundColor=[UIColor whiteColor];
	}
	return self;
}
-(void)dealloc{
	[super dealloc];
}
-(void)drawRect:(CGRect)rect{
	UIFont *font = [UIFont systemFontOfSize:30];
	[@"Hello World" drawAtPoint:CGPointMake(0, 0) withFont:font];
}
@end

■エミュレータ

ビルドと実行をクリックする。

iPhoneアプリの開発環境を構築する

■開発者登録

Apple Developerに登録する。天下のappleだけあって入力項目が多い。

■iOS SDK

iOS Dev Centerから、Xcode 3.2.5 and iOS SDK 4.2(3.5GB以上)をダウンロードする。完了したらインストールする。

■インストール

初期状態のままOKを押して進めば良い。androidの開発環境をセットアップするよりもシンプルっちゃシンプル。

macでandroidの開発環境を構築する

■SDK

androidの開発者サイトからSDKをダウンロードしてくる。展開し以下のコマンドを実行する。

mv /Users/<user>/Downloads/android-sdk-mac_x86 /Users/<user>/

以下のコマンドを実行する。

/Users/<user>/android-sdk-mac_x86/tools/android update sdk

後は大体OKを押せばOK!

■eclipse

「ヘルプ > 新規ソフトウェアのインストール」で「作業対象」欄に以下のURLを入力する。

https://dl-ssl.google.com/android/eclipse/

インストールしeclipseを再起動したら、「eclipse > 環境設定 > android」で「SDKロケーション」に「/Users//android-sdk-mac_x86」と入力する。

後はお好みの設定にするだけ!(windowsでの開発環境構築

macでsuする

以下のコマンドでrootのパスワードを設定する。

sudo passwd root

設定したパスワードでsuできるようになる。打ち間違えないようにすること。

Javaのクラスとオブジェクト

■クラス

メンバ

フィールド
クラスやそのオブジェクトに付属するデータ変数で状態保持などに使用
メソッド
オブジェクトの振る舞いを定義
ネストしたクラス(インターフェース)
入れ子になっているクラスやインターフェースの宣言
class Body {

    // フィールド
    public long number;

    // メソッド
    public void hello(String str) {
        
    }

    // ネストしたクラス
    public class {
        
    }
}

■フィールド

以下のようにしてフィールドを初期化することができる。

class Body {
    double zero  = 0.0;
    double sum   = 1.1 + 2.2;
    double zero2 = zero;
    double four  = Math.sqrt(2);
    Dog pochi    = new Dog();
}

但し、例外を投げるような処理を右辺に書くことはできない。フィールドが初期化されなかった場合、型に応じたデフォルトの初期値が代入される。

boolean false
char ‘\u0000’
byte, short, int, long 0
float, double +0.0
オブジェクト参照 null

個人的には明示しておいた方が読みやすいと思う。

staticフィールド

実体が1つだけのフィールドを実現する。クラス変数とも呼ばれる。

class Dog {
    long nextID = 0;// コンストラクタで生成ごとに+するとか
}

finalフィールド

初期化後に「不変」であるフィールド。

class Dog {
    int numOfLegs = 4;// 変わらないよ
}
  • オブジェクトの不変な属性であるか
  • オブジェクトが生成されたときに決まっているか
  • オブジェクトが生成されたときに任意の値を設定するのは実用的かつ適切か

■アクセス制御

private
クラス自身からのみアクセス可能
修飾子無し
同一パッケージ内からアクセス可能
protected
クラス自身とサブクラスからアクセス可能
public
メンバーが定義されているクラスにアクセスできるクラスからアクセス可能

privateとprotected

メンバのみに指定可能。メンバ以外のクラスやインターフェースには指定不可。

publicとprotected

制御が及ばないコードによって自身の実装の変更が不可能になる可能性がある。

パッケージアクセスとprivate

実装の一部であり外部のクラスから隠蔽される。

パッケージ

同一パッケージのクラスは関連しているべきである。

■オブジェクトの生成と初期化

// オブジェクトを参照する変数の宣言で生成はしてない
Dog shiro;
// 生成を伴う
Dog pochi = new Dog();

コンストラクタ

newによってオブジェクトが返される前に実行される。

class Dog {
    private String mName;
    Dog(String name) {
        mName = name;
    }
}
  • 引数をとることができる
  • クラス名と同名である
  • アクセス修飾可能である
  • クラスのメンバではない

コンストラクタは複数定義することが可能であり、以下のように自身のコンストラクタをinvokeすることもできる。

class Dog {
    private String mName;
    Dog() {
        // 任意の処理
    }
    Dog(String name) {
        this();
        mName = name;
    }
}

publicでないコンストラクタはオブジェクトを生成できるクラスを制限できる。

メモ

  • 生成時に必要な領域を割り当てて領域を初期化し新しいオブジェクトへの参照を返す
  • 生成時に必要な空きメモリを確保できない場合はOutOfMemoryError例外を投げる
  • 生成にはnewを用いるが明示的に削除はせず、GCを使用してメモリ管理する
  • オブジェクトが不要になった場合、そのオブジェクトを参照しないようにしなければならない
  • メソッド内のローカル変数ならばメソッドの処理が終わるだけで参照されなくなる
  • フィールドのような場合はnullを代入することで参照されなくなる

■初期化ブロック

以下のようにすることでコンストラクタよりも前に複雑な処理を行うことができる。

class Dog {
    private String mName;
    {
        // 任意の処理
    }
    Dog(String name) {
        mName = name;
    }
    public String cry() {
        return "bow";
    }
}

コンストラクタを持つことができない無名内部クラスを書く場合に有用である。

  • 複数のブロックを記述することができる
  • 例外aを投げることができる(全てのコンストラクタがaの例外を投げると宣言されているときに限る)

初期化ブロックをstaticで修飾することもできる。


■メソッド

staticメソッド

クラスメソッドのこと。staticメソッドからはstaticでないメンバにはアクセスできない。

class Util {
    private String str1 = "sample1";// helloメソッドからアクセス不可能
    private static String str2 = "sample2";// helloメソッドからアクセス可能
    public static String hello() {
        return "Hello!"
    }
}

メソッドの呼び出し

メソッドはドット演算子を使用し、参照を通してオブジェクトに対する操作として呼び出される。

reference.method(arguments);

インスタンスメソッドの呼び出しは以下のようになる。

Dog pochi = new Dog("Pochi");
pochi.cry();

staticメソッド(クラスメソッド)の呼び出しは以下のようになる。

String hello = Util.hello();
toStringメソッド

オブジェクトの状態を表す文字列表現を返すメソッド。

class Dog {
    private String mName;
    {
        // 任意の処理
    }
    Dog(String name) {
        mName = name;
    }
    public String cry() {
        return "bow";
    }
    @Override
    public String toString() {
        return "Dog{name : " + mName + "}";
    }
}

可変長引数を持つメソッド

メソッドの最後の引数は、特定の型のシーケンスであることを宣言できる。

class Mail {
    public static void send(String... to) {
        for(int i = 0; i < to.length; i++)
    }
}

メソッドの実行と戻り値

以下の条件の時に、メソッドの処理が終了する。

return文が実行される
一つの宣言された戻り値型に代入可能な値を返すか、例外を投げる必要がある
メソッドの終わりに処理が達する
戻り値型はvoidとなる
catchできない例外が投げられる
throwsを記述する必要がある

引き数の値

class PassRef {
    public static void main(String[] args) {
        Dog pochi = new Dog("Pochi");
        System.out.println(pochi.getName());
        commonName(pochi);
        System.out.println(pochi.getName());
        pochi = null;// おまけ
    }
    public static void commonName(Dog dogRef) {
        dogRef.name = "Shiro";
        dogRef = null;
    }
}
/*
Pochi
Shiro
*/

pochiと(commonName内の)dogRefは同じ実体のオブジェクトを参照しているので、nameを変更すると実体のオブジェクトのnameフィールドが変更される。

一方で、(commonName内の)dogRefは参照をコピーしたものであるため、nullを代入しても実体がnullにはならない。

ちなみにpochiにnullを代入すると実体を参照している変数がなくなるので、GCの対象となる。

  • 引き数は全て値渡しであり、オブジェクトは常に参照である
  • Javaに参照渡しというものは存在しない
  • 引き数の宣言時にfinalを指定して不変にできる

■this

フィールドの識別子が引き数と同名であることなどにより隠蔽されている時、カレントオブジェクトへの参照として使用する。

class Dog {
    private String name;
    Dog(String name) {
        this.name = name;
    }
    public String cry() {
        return this.name + " : bow";
    }
}

■メソッドのオーバーロード

メソッドはシグネチャ(名前とパラメータの数とパラメータの型)を持つ。従って、同名のメソッドを複数持つことが可能であり、このことをオーバーロードという。(オーバーライドとは違う)

class Dog {
    private String name;
    private int age;
    Dog(String name) {
        this.name = name;
    }
    Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

メソッドでなくコンストラクタでも同様である。但し、可変長引数を持つときは注意する必要がある。

■staticメンバー名のインポート

static double tanh(double x) {
    return (Math.exp(x) - Math.exp(-x)) / (Math.exp(x) + Math.exp(-x));
}

以下のようなstatic import文を用いることによって

import static java.lang.Math.exp

以下のように簡略化して可読性の高いコードを記述することができる。

static double tanh(double x) {
    return (exp(x) - exp(-x)) / (exp(x) + exp(-x));
}

オンデマンドstatic import文

コンパイラが知らない名前が見つかった場合、指定された型が特定の名前のstaticメンバを持つかどうか調べる。

import static java.lang.Math.*

タイプの手間を省くために使用するのではなく、可読性と明瞭性を改善する目的で使用する。

■mainメソッド

プログラムを起動する場合に実行される最初のメソッドでpublic static void main(String[] args)でなければならない。

class Echo {
    public static void mail(String[] args) {
        for(int i = 0; i < args.length; i++){
            System.out.println(args[i]);
        }
    }
}

以下のコマンドで実行することができる。

java Echo hoge fuga
#hoge
#fuga

個々のクラスはmainメソッドを持って構わないので、アプリケーションは複数のmainメソッドを持つことができる。

■nativeメソッド

Javaで書かれていない既存のコードを使用するプログラムを書く必要がある場合やハードウェアを直接操作する必要がある場合、JavaからCやC++で記述されたメソッドを呼び出すことができる。

public native int getCPUID();

ネイティブメソッドはfinal, static, synchronized, public, protected, privateで修飾することができるが、abstract, strictfpで修飾することはできない。

JavaScriptでダイクストラ法(行列)

前回の記事では、生成するグラフが疎であったので連結リストを使用した。密グラフ向けに行列でも実装した。

■実装

// Graph //(密ではないが)前回のグラフと同じグラフを使用
var Vertexes = [
             [0, 1, 3, 0, 0, 0],// s
             [0, 0, 1, 4, 0, 0],// 1
             [0, 0, 0, 1, 0, 0],// 2
             [0, 0, 0, 0, 1,10],// 3
             [0, 0, 0, 0, 0, 1],// 4
             [0, 0, 0, 0, 0, 0] // g
];

// initialize
var dist    = [];
var pred    = [];
var visited = [];
for(var i = 0; i < Vertexes.length; i++){
    dist[i] = Number.POSITIVE_INFINITY;
    pred[i] = -1;
    visited[i] = false;// 訪問を記録する
}
dist[0] = 0;// start

// search
var dijkstraMX = function(){
    var getMin = function(){
        var tmp = Number.POSITIVE_INFINITY;
        for(var i = 0; i < Vertexes.length; i++){
            if(visited[i] === false && dist[i] < tmp){
                tmp = i;
            }
        }
        if(tmp === Number.POSITIVE_INFINITY){
            tmp = null;
        }
        return tmp;
    }

    while(true){
        var u = getMin();// 未訪問の中でスタートから最小の距離の頂点
        // 「sから辿れない頂点しか残っていない場合」「未訪問が無い場合」はループ終了
        if(dist[u] === Number.POSITIVE_INFINITY || u === null){break;}
        visited[u] = true;
        for(var i = 0; i < Vertexes[u].length; i++){
            if(Vertexes[u][i] > 0){// 辺が存在している
                var neighbor  = i;//隣接点(a)
                var weight    = Vertexes[u][i];// (a)との辺の重み
                var newLength = dist[u] + weight;// (b)
                // 現在セットされている、スタート地点から隣接点までの距離が
                // 新しい経路での値より大きい時
                if(newLength < dist[neighbor]){
                    dist[neighbor] = newLength;
                    pred[neighbor] = u;
                }
            }
        }
    }
}
dijkstraMX();

// 最短経路
console.log(pred);// [-1, 0, 1, 2, 3, 4]

// 最短距離
console.log(dist);// [0, 1, 2, 3, 4, 5]

グラフが疎である場合、行列を使用すると殆どの空間が0で埋められるので勿体無いね。

eclipseでJavaScriptの単体テストをする

つまずいた部分があったのでメモっておく。φ(-ω-。`)。

■ダウンロード

eclipse downloadsのJavaScript版をダウンロードした。

■プラグイン

JsTestDriverを使用する。

まず、「ヘルプ > 新規ソフトウェアのインストール > 有効なソフトウェア・サイト」を選択し、フィルタに「http://js-test-driver.googlecode.com/svn/update/」と入力する。

次に、一覧にパッケージが表示されるので、バージョンが新しいものを選択しインストールする。

■使用方法

用意するファイルは3ファイルである。以下のサンプルソースはドキュメントのコードを使用させていただいた。

projectdir/src/Greeter.js

myapp = {};
myapp.Greeter = function(){ };
myapp.Greeter.prototype.greet = function(name){
    return "Hello " + name + "!";
};

projectdir/src/GreeterTest.js

テストコードである。

GreeterTest = TestCase("GreeterTest");

GreeterTest.prototype.testGreet = function(){
    var greeter = new myapp.Greeter();
    assertEquals("Hello World!", greeter.greet("World"));
};

projectdir/jsTestDriver.conf

クラスのディレクトリとテストコードのディレクトリを設定している感じだ。

server: http://localhost:42442

load:
  - src/*.js
  - src-test/*.js

どうやらプロジェクトルートに置く必要があるようだ。また、ファイル内のパスは注意して正しく記述する必要がある、

ビューの表示

「ウィンドウ > ビューの表示 > その他」を選択し、JavaScriptの中からJsTestDriverを選択すると表示される。

設定1

「ウィンドウ > 設定 > Js Test Driver」を選択し、各ブラウザのexeファイルと関連付ける。要はパスを通すって感じだ。

設定2

プロジェクトを選択した状態で、「実行 > 実行の構成」を選択したら、「実行 > Js Test Driver Test > 新規構成」を選択し、以下のように入力する。

project
projectdir
Conf File
jsTestDriver.conf

実行

JsTestDriverビューの「サーバーを始動」のボタンを押し、テストするブラウザのボタンを押す。するとブラウザが立ち上がるので、ビューに戻り「return last configuration」をクリックするとテストが実行される。

JavaScriptでダイクストラ法

優先度つきキューを使用したダイクストラ法をJavaScriptで実装した。

■実装

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.state    = 0;
    self.dist     = Number.POSITIVE_INFINITY;// もしくは十分に大きい値とか
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var g  = new Vertex(5);

// set up connections
// 単純化のためループや往路を除去した
s.appendNeighbor(
    {"weight" : 1, "vertex" : v1},
    {"weight" : 3, "vertex" : v2}
);
v1.appendNeighbor(
    {"weight" : 1, "vertex" : v2},
    {"weight" : 4, "vertex" : v3}
);
v2.appendNeighbor(
    {"weight" : 1, "vertex" : v3}
);
v3.appendNeighbor(
    {"weight" : 1, "vertex" : v4},
    {"weight" : 10, "vertex" : g}
);
v4.appendNeighbor(
    {"weight" : 1, "vertex" : g}
);
g.appendNeighbor(
);

// initialize
var vertexes = [s, v1, v2, v3, v4, g];
var pred     = [];
var pq       = new BinaryHeap();// sからの距離が短い頂点順の優先度つきキュー
s.dist = 0;
for(var i = 0; i < vertexes.length; i++){// キューの生成
    pred[i] = -1;
    pq.insert(vertexes[i], vertexes[i].dist);
}

// search
var dijkstraPQ = function(){
    while(pq.getList().length > 0){
        var u = pq.getPrior();// スタートからの距離が近い頂点を取得しcurrent頂点とする
        for(var i = 0; i < u.neighbor.length; i++){
            var neighbor  = u.neighbor[i].vertex;
            var weight    = u.neighbor[i].weight;// 隣接点の距離...(a)
            var newLength = u.dist + weight;// current頂点のsからの距離と(a)を加算...(b)
            // (b) < visitした時の距離の場合
            // キューを更新し、最短経路も更新する
            if(newLength < neighbor.dist){
                pq.changePriority(neighbor, newLength);
                neighbor.dist = newLength;
                pred[neighbor.value] = u.value;
            }
        }
    }
}
dijkstraPQ();

// 最短経路
console.log(pred);// [-1, 0, 1, 2, 3, 4]
// g<-v4<-v3-<v2<-v1<-s

// 最短距離
console.log(g.dist);// 5

任意の頂点に対して一つ前の頂点とその時の距離が分かる。

■特性

  • 辺の重みは0より大きい値
  • 重みの和が0より小さい閉路が存在すると無限ループする可能性がある

優先度つきキューについて

前回の記事のコードをそのまま使用した。

/**
 * BinaryHeap
 */
var BinaryHeap = function(){
    var self = this;
    self._ary  = [];
}
BinaryHeap.prototype._build = function(){
    var self = this;
    /**
     * heapify
     * 3要素を比較し最も小さい要素を親とする
     * @param {array} ary
     * @param {int} i
     * @param {max} max
     */
    var heapify = function(ary, i, max){
        /**
         * swap
         * @param {array} ary
         * @param {int} x
         * @param {int} y
         */
        var swap = function(ary, x, y){
            var a = ary[x];
            var b = ary[y];
            ary[x] = b;
            ary[y] = a;
            return true;
        }
        
        var l = 2 * i + 1;
        var r = 2 * i + 2;
        var li = 0;
        if(l < max && ary[l].priority < ary[i].priority){
            li = l;
        }
        else{
            li = i;
        }
        if(r < max && ary[r].priority < ary[li].priority){
            li = r;
        }
        if(li !== i){
            swap(ary, i, li);
            heapify(ary, li, max);
        }
    }
    var ary = self._ary;
    for(var i = ary.length - 1; i >= 0; i--){
        heapify(ary, i, self._ary.length);
    }
}
/**
 * BinaryHeap::insert
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.insert = function(elm, priority){
    var self = this;
    self._ary.push({
        "priority" : priority,
        "elm"      : elm
    });
    self._build();
}
/**
 * BinaryHeap::changePriority
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.changePriority = function(elm, priority){
    var self = this;
    var ary  = self._ary;
    for(var i = 0; i < ary.length; i++){
        if(elm === ary[i]["elm"]){
            ary[i]["priority"] = priority;
            self._build();
            return true;
        }
    }
    return false;
}
/**
 * BinaryHeap::getPrior
 */
BinaryHeap.prototype.getPrior = function(){
    var self = this;
    var elm  = self._ary.shift();
    self._build();
    return elm["elm"];
}
/**
 * BinaryHeap::getList
 */
BinaryHeap.prototype.getList = function(){
    var self = this;
    return self._ary;
}

JavaScriptで二分ヒープ(優先度つきキュー)

Cの場合は以下のようにして、二分ヒープを使用することができるらしい。

#include "BinaryHeap.h"

■実装

しかし、JavaScriptには二分ヒープのようなデータ構造が存在しないので、以下のように自力で実装する。

/**
 * BinaryHeap
 */
var BinaryHeap = function(){
    var self = this;
    self._ary  = [];
}
BinaryHeap.prototype._build = function(){
    var self = this;
    /**
     * heapify
     * 3要素を比較し最も小さい要素を親とする
     * @param {array} ary
     * @param {int} i
     * @param {max} max
     */
    var heapify = function(ary, i, max){
        /**
         * swap
         * @param {array} ary
         * @param {int} x
         * @param {int} y
         */
        var swap = function(ary, x, y){
            var a = ary[x];
            var b = ary[y];
            ary[x] = b;
            ary[y] = a;
            return true;
        }
        
        var l = 2 * i + 1;
        var r = 2 * i + 2;
        var li = 0;
        if(l < max && ary[l].priority < ary[i].priority){
            li = l;
        }
        else{
            li = i;
        }
        if(r < max && ary[r].priority < ary[li].priority){
            li = r;
        }
        if(li !== i){
            swap(ary, i, li);
            heapify(ary, li, max);
        }
    }
    var ary = self._ary;
    for(var i = ary.length - 1; i >= 0; i--){
        heapify(ary, i, self._ary.length);
    }
}
/**
 * BinaryHeap::insert
 * 要素をヒープに追加する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.insert = function(elm, priority){
    var self = this;
    self._ary.push({
        "priority" : priority,
        "elm"      : elm
    });
    self._build();
}
/**
 * BinaryHeap::changePriority
 * 要素の優先度を変更する
 * @param {Object} elm
 * @param {int} priority
 */
BinaryHeap.prototype.changePriority = function(elm, priority){
    var self = this;
    var ary  = self._ary;
    for(var i = 0; i < ary.length; i++){
        if(elm === ary[i]["elm"]){
            ary[i]["priority"] = priority;
            self._build();
            return true;
        }
    }
    return false;
}
/**
 * BinaryHeap::getPrior
 * 優先度の高い要素を取得する
 */
BinaryHeap.prototype.getPrior = function(){
    var self = this;
    var elm  = self._ary.shift();
    self._build();
    return elm["elm"];
}
/**
 * BinaryHeap::getList
 * ヒープを返す
 */
BinaryHeap.prototype.getList = function(){
    var self = this;
    return self._ary;
}

// test code
var pq = new BinaryHeap();
pq.insert('pochi', 0);
pq.insert('son', 4);
pq.insert('mike', 10);
pq.insert('father', 1);
pq.insert('mother', 2);
console.log(pq.getList());

優先度つきキューに使用したいので、ヒープソートのコードを変更し最小ヒープとした。使用方法は以下のとおりである。

二分ヒープの生成

var pq = new BinaryHeap();

要素の追加

pq.insert(elm, priority);

優先度の変更

pq.changePriority(elm, priority);

最優先要素の取得

var elm = pq.getPrior();

JavaScriptで幅優先探索

/**
 * Vertex
 * @param int value
 */
var Vertex = function(value){
    var self = this;
    self.value    = value;
    self.state    = 0;
    self.neighbor = [];
    self.appendNeighbor = function(){
        for(var i = 0; i < arguments.length; i++){
            self.neighbor.push(arguments[i]);
        }
    }
}

// set up a graph
var s  = new Vertex(0);
var v1 = new Vertex(1);
var v2 = new Vertex(2);
var v3 = new Vertex(3);
var v4 = new Vertex(4);
var v5 = new Vertex(5);
var v6 = new Vertex(6);
var v7 = new Vertex(7);
var v8 = new Vertex(8);
var g  = new Vertex(9);
s.appendNeighbor(v1, v4);
v1.appendNeighbor(s, v2);
v2.appendNeighbor(v1, v3);
v3.appendNeighbor(v2, v4, g);
v4.appendNeighbor(v3, v5, s);
v5.appendNeighbor(v4);
v6.appendNeighbor(v7);
v7.appendNeighbor(v6);
g.appendNeighbor(v3);
var vertexes = [s, v1, v2, v3, v4, v5, v6, v7, v8, g];

// initialize
var pred       = [];
var distance   = [];
var queue = [];
var counter    = 0;
for(var i = 0; i < vertexes.length; i++){
    pred[vertexes[i].value]       = -1;
    distance[vertexes[i].value]   = -1;
}

// search
s.state = 1;
distance[s.value] = 0;
queue.push(s);
var breadthFirstSearch = function(){
    while(queue.length > 0){
        var vertex = queue.shift();// 処理する頂点
        for(var i = 0; i < vertex.neighbor.length; i++){// 隣接点全てに対して
            var n = vertex.neighbor[i];
            if(vertex.neighbor[i].state === 0){
                distance[n.value] = distance[vertex.value] + 1;// 処理中の頂点+1の距離
                pred[n.value]     = vertex.value;// 処理中の頂点の値
                n.state           = 1;// visitした記録
                queue.push(n);// 隣接点をキューに入れる
            }
        }
        vertex.state = 2;// 処理し終わった記録
    }
}
breadthFirstSearch();

// 1つ前の節点の値
console.log(pred);// [-1, 0, 1, 4, 0, 4, -1, -1, -1, 3]

// 各節点のスタートからの距離
console.log(distance);// [0, 1, 2, 2, 1, 2, -1, -1, -1, 3]

console.log(vertexes);

スタート地点から全体に探索菌が同速度で広がっていくイメージだね。

■特性

  • 無向グラフでも有向グラフでも機能する
  • 重みでなくステップ数での最短距離を求めることができる
  • 節点をQueueに蓄えるので巨大グラフでは巨大なストレージが必要となる
  • スタートから辿れない頂点は基本的には訪問しない