在社群網路中找Fiona是否是Adm的朋友的朋友的~~的朋友

// 字典

function Dict(elements) {

    // 允許選擇性的初始對映表

    this.elements = elements || {};

}

Dict.prototype.has = function (key) {

    // 只有自有特性 (own property)

    return {}.hasOwnProperty.call(this.elements, key);

};

Dict.prototype.get = function (key) {

    // 只有自有特性

    return this.has(key) ? this.elements[key] : undefined;

};

Dict.prototype.set = function (key, val) {

    return this.elements[key] = val;

};

Dict.prototype.remove = function (key) {

    delete this.elements[key];

};

// 任意挑選集合元素

Dict.prototype.pick = function () {

    for (var key in this.elements) { // 這裡的elements是Member實體

        if (this.has(key)) {

            return key;

        }

    }

    throw new Error("空的字典");

};

// 為了避免字典被汙染, 所以建立一個工作集, 把字典放在這個類別中, 用來追蹤目前集合中的元素項目

function WorkSet() {

    this.entries = new Dict();

    this.count = 0;

}

WorkSet.prototype.isEmpty = function () {

    return this.count === 0;

};

WorkSet.prototype.add = function (key, val) {

    if (this.entries.has(key)) {

        return;

    }

    this.entries.set(key, val);

    this.count++;

};

WorkSet.prototype.get = function (key) {

    return this.entries.get(key);

};

WorkSet.prototype.remove = function (key) {

    if (!this.entries.has(key)) {

        return;

    }

    this.entries.remove(key);

    this.count--;

};

WorkSet.prototype.pick = function () {

    return this.entries.pick();

};

// 社交網路成員

function Member(name) {

    this.name = name;

    this.friends = [];

}

// 關聯朋友 方法1:用一個while迴圈來實作, 每次從集合中挑選出一個任意的元素, 並從work-set中移除

Member.prototype.inNetworkSet = function (other) {

    var visited = {};

    var workset = new WorkSet();

    workset.add(this.name, this); // 呼叫者的名子當 key, 用來先查找該呼叫者的朋友

    while (!workset.isEmpty()) {

        var name = workset.pick(); // 取出 key

        var member = workset.get(name);

        workset.remove(name);

        if (name in visited) { // 不要重新訪問成員

            continue;

        }

        visited[name] = member;

        if (member === other) { // 找到成員

            return true;

        }

        member.friends.forEach(function (friend) {

            workset.add(friend.name, friend);

        });

    }

    return false;

};

// 關聯朋友 方法2:將工作項目存到陣列中而非一個集合(set)中, 以完全相同的順序來巡訪社交網路路線

Member.prototype.inNetworkList = function (other) {

    var visited = {};

    var worklist = [this];

    while (worklist.length > 0) {

        var member = worklist.pop();

        if (member.name in visited) {// 不要重新訪問成員

            continue;

        }

        visited[member.name] = member;

        if (member === other) {

            return true;

        }

        member.friends.forEach(function (friend) {

            worklist.push(friend); // 加入工作清單

        });

    }

    return false;

};

var a = new Member("Adm"),

    b = new Member("Bob"),

    c = new Member("Chris"),

    d = new Member("David"),

    e = new Member("Eason"),

    f = new Member("Fiona");

a.friends.push(b);

b.friends.push(c);

c.friends.push(e);

d.friends.push(b);

e.friends.push(d, f); // a 和 f 關聯

console.log(a.inNetworkList(f));