成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

無(wú)厘頭 Graph

jayzou / 3229人閱讀

摘要：老孫到此一游對(duì)于深度遍歷，是將圖按一個(gè)固定方向，縱向的結(jié)果，所以是一個(gè)遞歸的結(jié)構(gòu)。老孫到此一游對(duì)于廣度遍歷，是將圖按一個(gè)固定方向，橫向的結(jié)果，所以是一個(gè)鏈?zhǔn)竭M(jìn)出的關(guān)系，這里是用隊(duì)列，在中做隊(duì)列這種先進(jìn)先出比較簡(jiǎn)單。

前言

今天晚上無(wú)意翻到一個(gè)圖的文章，查了一下感覺(jué)網(wǎng)上實(shí)現(xiàn)和其他都好復(fù)雜，所以自己按理解搞了一下，不知道是我實(shí)現(xiàn)是不是錯(cuò)了...感覺(jué)還好～進(jìn)入正題，先還是來(lái)點(diǎn)理論知識(shí)，不過(guò)大多是自己的想法，不一定都對(duì)，可以糾正。內(nèi)容來(lái)源來(lái)自《JavaScript 數(shù)據(jù)結(jié)構(gòu)和算法》。

圖

圖是一種數(shù)學(xué)模型，和數(shù)學(xué)掛勾一般都會(huì)比較復(fù)雜，所以形象的理解成最簡(jiǎn)單的模型，點(diǎn)-線(xiàn) 模型。其實(shí)最簡(jiǎn)單的是 1 個(gè)點(diǎn)的模型，涉及 2 個(gè)點(diǎn)還好，3 個(gè)點(diǎn)過(guò)后模型就會(huì)作出相應(yīng)的改變。

這里用簡(jiǎn)單的語(yǔ)言來(lái)說(shuō)圖中的二元關(guān)系，不過(guò)還是先假設(shè)一點(diǎn)數(shù)學(xué)符號(hào)：

G => 表示所有的頂點(diǎn)集合

V => 表示頂點(diǎn)

E => 表示邊，抽象意義上是無(wú)向邊

那么用數(shù)學(xué)來(lái)表示就是：G=

其實(shí)根本不用理解數(shù)學(xué)的模型，我這里理解是只需要知道這是一個(gè)點(diǎn)-線(xiàn)模型就可以了。

如何表示圖呢？

這里有兩種表示方法：表和矩陣，其間都是鄰接關(guān)系

這里我有一個(gè)測(cè)試圖，在網(wǎng)上弄的，雖然是無(wú)向圖，其實(shí)在我們代碼中，肯定是有向的，是入口的問(wèn)題：

圖的結(jié)構(gòu)確定過(guò)后，就可以做出表的結(jié)構(gòu)了，這里我沒(méi)有用方向，因?yàn)槲依斫獾膱D是一個(gè)不能簡(jiǎn)單表示的，理解成坐標(biāo)系更好理解一點(diǎn)。分為：x, y 軸的方式。其中，x0 表示開(kāi)始，后面表示相鄰的點(diǎn)，按順時(shí)針排列（不一定按這個(gè)順序）。

代碼中的圖

在代碼中表示，沒(méi)有圖形那么直觀，所以需要映射成代碼模型，這里簡(jiǎn)單實(shí)現(xiàn)一下，但是不具備很多功能。

假設(shè)：

class G => 一個(gè)圖的類(lèi)，包括圖的定義和常用遍歷方法

this.V => 表示點(diǎn)集合的個(gè)數(shù)，但是這里我舍棄了 0 的位置

this.T => 我按數(shù)據(jù)庫(kù)表的方式理解命名的，關(guān)系的集合

this.E => 邊的個(gè)數(shù)

this.visited => 訪(fǎng)問(wèn)過(guò)的 bool 集合，其實(shí)就是標(biāo)記

this.defined => 工具小函數(shù)，是否定義過(guò)，與圖無(wú)關(guān)

所以最后有關(guān)的符號(hào)有：

G、V、T、E

是不是感覺(jué)一下子變簡(jiǎn)單了，不過(guò)程序的抽象有一個(gè)上層，那就是類(lèi)。
然后我這里按計(jì)算機(jī)的方式，定義了輸入、輸出函數(shù)：input、output

class G {
    constructor(V) {
        this.V = V;
        this.T = [];
        this.E = 0;
        this.visited = [];

        for (let v = 0; v < this.V; ++v) {
            this.T[v] = [];
            this.T[v].push(-1);
        }

        this.defined = s => s !== void 0;
    }
    input(v, w) {
        this.T[v].push(w);
        this.T[w].push(v);

        this.E++;

        return this;
    }
    output() {
        console.table(this.T);
    }
}

然后能夠看出，其實(shí)邊是由點(diǎn)的連接組成的，剛好符合數(shù)學(xué)的定義，并且與相鄰有相關(guān)性。

那么，實(shí)現(xiàn)了結(jié)構(gòu)，還應(yīng)該有其他作用，那么接下來(lái)看一下遍歷算法：深度遍歷（DFS） 和 廣度遍歷（BFS）。準(zhǔn)確來(lái)說(shuō)應(yīng)該是優(yōu)先采用什么策略的遍歷方式。其實(shí)我這里的實(shí)現(xiàn)感覺(jué)...不好，和樹(shù)關(guān)系大了點(diǎn)，不過(guò)樹(shù)的大集合就能夠上升到圖。

dfs(v) {
    this.visited[v] = true;

    if (this.defined( this.T[v] )) {
        console.log("老孫到此一游：" + v);
    }

    this.T[v].forEach(t => {
        if (t !== -1 && !this.visited[t]) {
            this.dfs(t);
        }
    });
}

對(duì)于深度遍歷，是將圖按一個(gè)固定方向，縱向的結(jié)果，所以是一個(gè)遞歸的結(jié)構(gòu)。

bfs(node) {
    this.visited[node] = true;

    var queue = [];
    queue.push(node);
    while(queue.length > 0) {
        var v = queue.shift();
        if(this.defined( this.T[v] )) {
            console.log("老孫到此一游：" + v);
        }

        this.T[v].forEach(t => {
            if(t !== -1 && !this.visited[t]) {
                this.visited[t] = true;
                queue.push(t);
            }
        });
    }
}

對(duì)于廣度遍歷，是將圖按一個(gè)固定方向，橫向的結(jié)果，所以是一個(gè)鏈?zhǔn)竭M(jìn)出的關(guān)系，這里是用隊(duì)列，在 JS 中做隊(duì)列這種先進(jìn)先出比較簡(jiǎn)單。

// 測(cè)試代碼
var v = [1, 2, 3, 4, 5];
let g = new G( v.length + 1 );
g.input(1, 2).input(1, 5)
    .input(2, 4).input(2, 5).input(2, 3)
    .input(3, 4)
    .input(4, 5)
    .output();
g.dfs(1);
console.log("------------");
// 讓它失憶一下
g.visited = [];
g.bfs(1);

……-_-# 簡(jiǎn)單玩一下，睡覺(jué)了 zZZ

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/91260.html

相關(guān)文章

  • 徹底理解z-index，看完還是只會(huì)無(wú)厘頭的設(shè)置9999你打我~~~~

    摘要：如果同級(jí)父元素不是層疊上下文元素就不需要看父元素的眼色了文章到這里就結(jié)束了，希望看完這篇文章的同學(xué)可以徹底理解。 今天寫(xiě)代碼用antd-mobile的checkbox時(shí)候，想在內(nèi)容文本后面添加一個(gè)icon，并且需要對(duì)這個(gè)icon綁定事件，發(fā)現(xiàn)綁定之后怎么也點(diǎn)不中，調(diào)試發(fā)現(xiàn)原來(lái)被層層嵌套的dom元素蓋住了，肯定是z-index在作祟。可是按照我之前對(duì)z-index的了解（自信滿(mǎn)滿(mǎn)）卻怎么...

    bladefury 評(píng)論0 收藏0

  • 徹底理解z-index，看完還是只會(huì)無(wú)厘頭的設(shè)置9999你打我~~~~

    摘要：如果同級(jí)父元素不是層疊上下文元素就不需要看父元素的眼色了文章到這里就結(jié)束了，希望看完這篇文章的同學(xué)可以徹底理解。 今天寫(xiě)代碼用antd-mobile的checkbox時(shí)候，想在內(nèi)容文本后面添加一個(gè)icon，并且需要對(duì)這個(gè)icon綁定事件，發(fā)現(xiàn)綁定之后怎么也點(diǎn)不中，調(diào)試發(fā)現(xiàn)原來(lái)被層層嵌套的dom元素蓋住了，肯定是z-index在作祟?？墒前凑瘴抑皩?duì)z-index的了解（自信滿(mǎn)滿(mǎn)）卻怎么...

    RobinTang 評(píng)論0 收藏0

  • js下探究 let, var 之于閉包

    摘要：?jiǎn)栴}在說(shuō)閉包，一定會(huì)牽涉到作用域。這也是閉包的屬性的，能夠記錄下內(nèi)部函數(shù)引用外部的值。因?yàn)槎际侨肿兞?，所以循環(huán)也就是不斷值覆蓋，閉包并不會(huì)記錄在循環(huán)時(shí)的值，只會(huì)記錄閉包變量。閉包時(shí)記錄的除了閉包變量還有塊級(jí)作用域變量最后來(lái)看看這個(gè)輸出什么 js 是非常靈活的語(yǔ)言，寫(xiě)起來(lái)真是* 不過(guò)現(xiàn)在有了typescript，寫(xiě)起來(lái)舒服多了。 問(wèn)題 在說(shuō)js閉包，一定會(huì)牽涉到作用域。而一般在區(qū)別 v...

    BLUE 評(píng)論0 收藏0

  • 微信小程序項(xiàng)目總結(jié)（一）

    摘要：前言微信小程序的開(kāi)發(fā)，我應(yīng)該算是趕上了第一波，所以，自然是一路踩坑而來(lái)。注以下標(biāo)題是按照微信開(kāi)發(fā)工具上的選項(xiàng)進(jìn)行劃分的。不過(guò)，除此之外，它還會(huì)產(chǎn)生另外一個(gè)副作用，就是可能連小程序本身上的請(qǐng)求都請(qǐng)求不了了。 -- KChris 2017.3.16 (=^.^=) 前言微信小程序的開(kāi)發(fā)，我應(yīng)該算是趕上了第一波，所以，自然是一路踩坑而來(lái) =。=一月九日，小程序正式上線(xiàn)，早早地就到公司開(kāi)始改b...

    whatsns 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<