無厘頭 Graph

jayzou 發(fā)布于2019-08-22 10:47 / 3186人閱讀

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

前言

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

圖

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

這里用簡單的語言來說圖中的二元關(guān)系，不過還是先假設(shè)一點數(shù)學(xué)符號：

G => 表示所有的頂點集合

V => 表示頂點

E => 表示邊，抽象意義上是無向邊

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

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

如何表示圖呢？

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

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

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

代碼中的圖

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

假設(shè)：

class G => 一個圖的類，包括圖的定義和常用遍歷方法

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

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

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

this.visited => 訪問過的 bool 集合，其實就是標(biāo)記

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

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

G、V、T、E

是不是感覺一下子變簡單了，不過程序的抽象有一個上層，那就是類。
然后我這里按計算機的方式，定義了輸入、輸出函數(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ù)學(xué)的定義，并且與相鄰有相關(guān)性。

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

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);
        }
    });
}

對于深度遍歷，是將圖按一個固定方向，縱向的結(jié)果，所以是一個遞歸的結(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);
            }
        });
    }
}

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

// 測試代碼
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);

……-_-# 簡單玩一下，睡覺了 zZZ