国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

最小生成樹原理及Kruskal算法的js實(shí)現(xiàn)

scq000 / 2665人閱讀

摘要：生成樹和最小生成樹的概念設(shè)圖連通，則生成樹包含圖中的所有節(jié)點(diǎn)，及條邊的連通圖，一個(gè)圖的生成樹可以有多顆最小生成樹最小權(quán)重生成樹，在生成樹的概念上加一個(gè)限制條件，即生成樹的所有邊的權(quán)值總和最小的樹，最小生成樹也可以有多顆求解最小生成樹的通用

1. 生成樹和最小生成樹的概念

設(shè)圖G(V,E)連通，則
生成樹：包含圖G(V,E)中的所有節(jié)點(diǎn)，及|V|-1條邊的連通圖，一個(gè)圖的生成樹可以有多顆
最小生成樹：最小權(quán)重生成樹，在生成樹的概念上加一個(gè)限制條件，即生成樹的所有邊的權(quán)值總和最小的樹，最小生成樹也可以有多顆

2. 求解最小生成樹的通用方法

由于最小生成樹包含圖G的所有邊，所以我們需要做的只是尋找最小生成樹的邊集A

設(shè)：邊集A是圖G的任意一顆最小生成樹的邊的子集，初始時(shí)A為空當(dāng)A不等于G的某個(gè)最小生成樹的所有邊集M時(shí)循環(huán)以下步驟 找到一條屬于M但不屬于A的邊，加入到A中

現(xiàn)在問題我們?nèi)绾稳ふ夷菞l只屬于M但不屬于A的邊

邊v的尋找方法
當(dāng)A為空時(shí)，圖G(V,A)是一個(gè)有|V|個(gè)樹的森林，當(dāng)A中有n條邊時(shí)，n<|V|-1,圖G是一個(gè)有|V|-(n+1)個(gè)樹的森林，我們需要尋找的邊v的加入會(huì)導(dǎo)致圖G中的森林?jǐn)?shù)目減1邊v是這樣一條邊

邊v的兩端的節(jié)點(diǎn)屬于兩顆不同的樹

邊v的權(quán)值是所有滿足以上條件中權(quán)值最小的

3. Kruskal和Prim 算法

Kruskal和Prim 算法是最小生成樹常用的兩種算法，這兩種算法都是對(duì)上述通用方法的細(xì)化，不同之處就是對(duì)邊v的尋找方法上有所差異，Kruskal算法又叫做(邊擴(kuò)展)算法，適用于邊稀疏的圖，Prim算法叫做(節(jié)點(diǎn)擴(kuò)展算法)，適用于邊稠密的圖

4. Kruskal算法

4.1. 概念
Kruskal算法的特點(diǎn)是上述A中的邊可以屬于多顆不同的樹

4.2. 輔助函數(shù) MakeSet(x)

MakeSet操作創(chuàng)建一個(gè)包含|V|顆樹的集合，每顆樹只包含一個(gè)節(jié)點(diǎn)，我們要為每個(gè)節(jié)點(diǎn)x添加兩個(gè)屬性

 var MakeSet = (function(){
    let set = new Set();
    return function(x) {
        x.parent = x;
        x.rank = 0;
        if(!set.has(x)) set.add(x);
        return set;
    }
})();

4.3. 輔助函數(shù) Find(x)

找到并返回x節(jié)點(diǎn)所在的那顆樹的根節(jié)點(diǎn)，用于判斷兩個(gè)節(jié)點(diǎn)是否在同一顆樹中，即是否相交

 function Find(x) {
    if (x.parent != x)
        x.parent = Find(x.parent);
    return x.parent;
}

4.4. 輔助函數(shù) Union(u, v)

Union函數(shù)旨在合并兩個(gè)節(jié)點(diǎn)，應(yīng)該將這里的合并和在圖G中的連通區(qū)分開，我們通過不斷調(diào)用union來改變MakeSet集合中元素的連通性，被合并的兩個(gè)節(jié)點(diǎn)會(huì)變成一顆數(shù),當(dāng)然讀者也可以實(shí)現(xiàn)自己的Union,隨意實(shí)現(xiàn)都行，只有調(diào)用Union操作之后改變了MakeSet,中圖的連通性，是的u，v節(jié)點(diǎn)處于同一顆樹就行,本文的Union方法采用的思想是 按秩合并(秩 rank)、路徑壓縮 ，通過這種方式創(chuàng)建的樹的節(jié)點(diǎn)分布,會(huì)比較均勻，平衡性較高，也就導(dǎo)致操作效率很高

function Union(u, v) {
    let uRoot = Find(u);
    let vRoot = Find(v);
    // 如果 u 和 v 在同一顆樹
    if (uRoot == vRoot) return;
    // 如果 u 和 v 不在同一顆樹中，合并它們
    // 如果 uRoot 的層級(jí)比 vRoot 的小,將 uRoot 作為 vRoot 前驅(qū)節(jié)點(diǎn)
    if (uRoot.rank < vRoot.rank) uRoot.parent = vRoot;
    // 如果 uRoot 的層級(jí)比 vRoot 的大,將 vRoot 作為 uRoot 前驅(qū)節(jié)點(diǎn)
    else if (uRoot.rank > vRoot.rank) vRoot.parent = uRoot;
    //將 uRoot 設(shè)置為根節(jié)點(diǎn),并將 uRoot 的層級(jí)加一
    else {
        vRoot.parent = uRoot;
        uRoot.rank = uRoot.rank + 1;
    }
}

4.5. Kruskal算法

Kruskal算法旨在尋找最小生成數(shù)中包含哪些邊,在后面的完整代碼中，該函數(shù)的實(shí)現(xiàn)會(huì)有所不同，這里著重體會(huì)原理

function Kruskal(G, w) {
    let A = []; //A用于存放最小生成數(shù)所包含的邊
    for(let x of G.V) {
        MakeSet(x);
    }
    //對(duì)G.E按照邊的權(quán)中從小到大排序
    for(let e of G.E) {
        quickSort(0, G.E.length-1, G.E, "w");
    }
    //由于邊已經(jīng)按照從小到大的順序有序，所以這里只需要尋找不相交的邊(邊所在的樹不相交)，
    for(let e of G.E) {
        if(Find(e.u)!=Find(e.v)) {
            A.push(e);
            Union(e.u, e.v); //改變連通性
        }
    }
    return A;
}

4.6. 圖，頂點(diǎn)，邊，的數(shù)據(jù)結(jié)構(gòu)

這里的數(shù)據(jù)結(jié)構(gòu)及如何建圖參照 BFS,DFS 算法原理及js實(shí)現(xiàn)，這里不做詳細(xì)說明

//頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)
function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.edges = null; //由頂點(diǎn)發(fā)出的所有邊
    this.id = null; //節(jié)點(diǎn)的唯一標(biāo)識(shí)
    this.data = null; //存放節(jié)點(diǎn)的數(shù)據(jù)
}

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    this.sibling = null;
    this.w = null; //保存邊的權(quán)值
}

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.V = []; //節(jié)點(diǎn)集
    this.E = []; //邊集
    this.refer = new Map(); //字典 用來映射標(biāo)節(jié)點(diǎn)的識(shí)符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進(jìn)來的已經(jīng)具備了邊的關(guān)系
    //創(chuàng)建圖的 節(jié)點(diǎn)
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點(diǎn)并初始化節(jié)點(diǎn)屬性 id
        for (let v of vertexs) {
            let vertex = Vertex();
            vertex.id = v.id;
            this.V.push(vertex);
        }
        //初始化 字典
        for (let i in this.V) {
            this.refer.set(this.V[i].id, i);
        }
    },
    //建立圖中 邊 的關(guān)系
    initEdge: (function() {
        //創(chuàng)建鏈表，返回鏈表的第一個(gè)節(jié)點(diǎn)
        function createLink(index, len, edges, refer) {
            if (index >= len) return null;
            let edgeNode = Edge();
            edgeNode.index = refer.get(edges[index].id); //邊連接的節(jié)點(diǎn) 用在數(shù)組中的位置表示 參照字典
            edgeNode.w = edges[index].w; //邊的權(quán)值
            edgeNode.sibling = createLink(++index, len, edges, refer); //通過遞歸實(shí)現(xiàn) 回溯
            return edgeNode;
        }
        return function(edges) {
            for (let field in edges) {
                let index = this.refer.get(field); //從字典表中找出節(jié)點(diǎn)在 V 中的位置
                let vertex = this.V[index]; //獲取節(jié)點(diǎn)
                vertex.edges = createLink(0, edges[field].length, edges[field], this.refer);
            }
        }
    }()),
    storageEdge: function(edges) {
        this.E = edges;
    }
}

var vertexs = [{id:"a"}, {id:"b"}, {id:"c"}, {id:"d"}, {id:"e"}];
var edges = [
    {u:"a",v:"b",w:3},
    {u:"a",v:"c",w:1},
    {u:"b",v:"a",w:3},
    {u:"b",v:"c",w:4},
    {u:"b",v:"d",w:5},
    {u:"c",v:"a",w:1},
    {u:"c",v:"b",w:4},
    {u:"c",v:"d",w:6},
    {u:"c",v:"e",w:7},
    {u:"d",v:"b",w:5},
    {u:"d",v:"c",w:6},
    {u:"d",v:"e",w:2},
    {u:"e",v:"c",w:7},
    {u:"e",v:"d",w:6}
]

var g = Graph();
g.initVertex(vertexs);
g.storageEdge(edges);

運(yùn)行這部分代碼，生成了用于Kruskal算法輸入的圖

4.7. 完整代碼及測(cè)試

測(cè)試的算法的輸入圖為上圖，紅色的邊為最終最小生成樹包含的邊，出現(xiàn)順序依次為 ac,de,ab,bd,這里的輸入圖為無向圖

//快速排序 數(shù)組a由對(duì)象組成 key為排序的參照指標(biāo) quickSort(0,a.length-1,a,"key")
function quickSort(left, right, a, key) {
    if (left > right)
        return;
    var i = left;
    var j = right;
    var benchMark = a[i];
    var temp;
    while (i != j) {
        //移動(dòng) j
        while (a[j][key] >= benchMark[key] && i < j)
            j--;
        //移動(dòng) i
        while (a[i][key] <= benchMark[key] && i < j)
            i++;
        if (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    a[left] = a[i];
    a[i] = benchMark;
    quickSort(left, i - 1, a, key);
    quickSort(i + 1, right, a, key);
}

var MakeSet = (function() {
    let set = new Set();
    return function(x) {
        x.parent = x;
        x.rank = 0;
        if (!set.has(x)) set.add(x);
        return set;
    }
})();

//體會(huì)兩個(gè) Find 方法的不同
// function Find(x) {
//     if (x.parent != x)
//         Find(x.parent);
//     return x.parent;
// }

function Find(x) {
    if (x.parent != x)
        x.parent = Find(x.parent);
    return x.parent;
}

function Union(u, v) {
    let uRoot = Find(u);
    let vRoot = Find(v);
    // 如果 u 和 v 在同一顆樹
    if (uRoot == vRoot) return;
    // 如果 u 和 v 不在同一顆樹中，合并它們
    // 如果 uRoot 的層級(jí)比 vRoot 的小,將 uRoot 作為 vRoot 前驅(qū)節(jié)點(diǎn)
    if (uRoot.rank < vRoot.rank) uRoot.parent = vRoot;
    // 如果 uRoot 的層級(jí)比 vRoot 的大,將 vRoot 作為 uRoot 前驅(qū)節(jié)點(diǎn)
    else if (uRoot.rank > vRoot.rank) vRoot.parent = uRoot;
    //任選一個(gè)作為根節(jié)點(diǎn)
    else {
        vRoot.parent = uRoot;
        uRoot.rank = uRoot.rank + 1;
    }
}

function Kruskal(G) {
    let A = []; //A用于存放最小生成數(shù)所包含的邊
    for(let x of G.V) {
        MakeSet(x);
    }
    //對(duì)G.E按照邊的權(quán)中從小到大排序
    for(let e of G.E) {
        quickSort(0, G.E.length-1, G.E, "w");
    }
    for(let e of G.E) {
        let u = G.V[G.refer.get(e.u)];
        let v = G.V[G.refer.get(e.v)];
        if(Find(u)!=Find(v)) {
            A.push(e);
            Union(u, v);
        }
    }
    return A;
}

function Vertex() {
    if (!(this instanceof Vertex))
        return new Vertex();
    this.edges = null; //由頂點(diǎn)發(fā)出的所有邊
    this.id = null; //節(jié)點(diǎn)的唯一標(biāo)識(shí)
    this.data = null; //存放節(jié)點(diǎn)的數(shù)據(jù)
}

//數(shù)據(jù)結(jié)構(gòu) 鄰接鏈表-邊
function Edge() {
    if (!(this instanceof Edge))
        return new Edge();
    this.index = null; //邊所依附的節(jié)點(diǎn)的位置
    this.sibling = null;
    this.w = null; //保存邊的權(quán)值
}

//數(shù)據(jù)結(jié)構(gòu) 圖-G
function Graph() {
    if (!(this instanceof Graph))
        return new Graph();
    this.V = []; //節(jié)點(diǎn)集
    this.E = [];
    this.refer = new Map(); //字典 用來映射標(biāo)節(jié)點(diǎn)的識(shí)符和數(shù)組中的位置
}
Graph.prototype = {
    constructor: Graph,
    //這里加進(jìn)來的已經(jīng)具備了邊的關(guān)系
    //創(chuàng)建圖的 節(jié)點(diǎn)
    initVertex: function(vertexs) {
        //創(chuàng)建節(jié)點(diǎn)并初始化節(jié)點(diǎn)屬性 id
        for (let v of vertexs) {
            let vertex = Vertex();
            vertex.id = v.id;
            this.V.push(vertex);
        }
        //初始化 字典
        for (let i in this.V) {
            this.refer.set(this.V[i].id, i);
        }
    },
    //建立圖中 邊 的關(guān)系
    initEdge: (function() {
        //創(chuàng)建鏈表，返回鏈表的第一個(gè)節(jié)點(diǎn)
        function createLink(index, len, edges, refer) {
            if (index >= len) return null;
            let edgeNode = Edge();
            edgeNode.index = refer.get(edges[index].id); //邊連接的節(jié)點(diǎn) 用在數(shù)組中的位置表示 參照字典
            edgeNode.w = edges[index].w; //邊的權(quán)值
            edgeNode.sibling = createLink(++index, len, edges, refer); //通過遞歸實(shí)現(xiàn) 回溯
            return edgeNode;
        }
        return function(edges) {
            for (let field in edges) {
                let index = this.refer.get(field); //從字典表中找出節(jié)點(diǎn)在 V 中的位置
                let vertex = this.V[index]; //獲取節(jié)點(diǎn)
                vertex.edges = createLink(0, edges[field].length, edges[field], this.refer);
            }
        }
    }()),
    storageEdge: function(edges) {
        this.E = edges;
    }
}

//測(cè)試數(shù)據(jù)
var vertexs = [{id:"a"}, {id:"b"}, {id:"c"}, {id:"d"}, {id:"e"}];
var edges = [
    {u:"a",v:"b",w:3},
    {u:"a",v:"c",w:1},
    {u:"b",v:"a",w:3},
    {u:"b",v:"c",w:4},
    {u:"b",v:"d",w:5},
    {u:"c",v:"a",w:1},
    {u:"c",v:"b",w:4},
    {u:"c",v:"d",w:6},
    {u:"c",v:"e",w:7},
    {u:"d",v:"b",w:5},
    {u:"d",v:"c",w:6},
    {u:"d",v:"e",w:2},
    {u:"e",v:"c",w:7},
    {u:"e",v:"d",w:6}
]

var g = Graph();
g.initVertex(vertexs);
g.storageEdge(edges);
var A = Kruskal(g);
console.log(A);

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

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

相關(guān)文章

  • 【程序員必會(huì)十大算法】之Kruskal算法

    摘要：很好解決，采用排序算法進(jìn)行排序即可。處理方式是記錄頂點(diǎn)在最小生成樹中的終點(diǎn)，頂點(diǎn)的終點(diǎn)是在最小生成樹中與它連通的最大頂點(diǎn)。如何判斷回路將所有頂點(diǎn)按照從小到大的順序排列好之后，某個(gè)頂點(diǎn)的終點(diǎn)就是與它連通的最大頂點(diǎn)。 ...

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

  • 算法（第4版） Chapter 4.3 最小生成樹

    摘要：算法圖示代碼復(fù)雜度時(shí)間初始化優(yōu)先隊(duì)列，最壞情況次比較每次操作成本次比較，最多還會(huì)多次和次操作，但這些成本相比的增長數(shù)量級(jí)可忽略不計(jì)詳見空間 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter 4 Section 3 最小生成樹 定義 樹是特殊的圖 圖的生...

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

  • 【圖論】最小生成樹

    摘要：最小生成樹有兩種生成算法普里姆算法克魯斯克爾算法算法普利姆算法算法流程我的理解任選一個(gè)元素，作為起始點(diǎn)將起始點(diǎn)標(biāo)記為，代表該點(diǎn)已經(jīng)加入最小生成樹集合計(jì)算這個(gè)集合到未加入的各個(gè)點(diǎn)的距離選擇一個(gè)最小的距離點(diǎn)，加入集合，即標(biāo)記為已訪問更新集合到其 最小生成樹有兩種生成算法 Prim（普里姆算法） Kruskal（克魯斯克爾）算法 Prim 算法（普利姆算法） 算法流程：（我的理解）...

    ?xiaoxiao, 評(píng)論0 收藏0

  • 面試算法實(shí)踐與國外大廠習(xí)題指南

    摘要：面試算法實(shí)踐與國外大廠習(xí)題指南翻譯自維護(hù)的倉庫，包含了在線練習(xí)算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。面試算法實(shí)踐與國外大廠習(xí)題指南在線練習(xí)在線面試編程數(shù)據(jù)結(jié)構(gòu)鏈表即是由節(jié)點(diǎn)組成的線性集合，每個(gè)節(jié)點(diǎn)可以利用指針指向其他節(jié)點(diǎn)。 面試算法實(shí)踐與國外大廠習(xí)題指南 翻譯自 Kevin Naughton Jr. 維護(hù)的倉庫 interviews，包含了在線練習(xí)、算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和...

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

  • 數(shù)據(jù)結(jié)構(gòu)與算法——常用高級(jí)數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)

    摘要：前文數(shù)據(jù)結(jié)構(gòu)與算法常用數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)總結(jié)了基本的數(shù)據(jù)結(jié)構(gòu)，類似的，本文準(zhǔn)備總結(jié)一下一些常見的高級(jí)的數(shù)據(jù)結(jié)構(gòu)及其常見算法和對(duì)應(yīng)的實(shí)現(xiàn)以及應(yīng)用場(chǎng)景，務(wù)求理論與實(shí)踐一步到位。 前文 數(shù)據(jù)結(jié)構(gòu)與算法——常用數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn) 總結(jié)了基本的數(shù)據(jù)結(jié)構(gòu)，類似的，本文準(zhǔn)備總結(jié)一下一些常見的高級(jí)的數(shù)據(jù)結(jié)構(gòu)及其常見算法和對(duì)應(yīng)的Java實(shí)現(xiàn)以及應(yīng)用場(chǎng)景，務(wù)求理論與實(shí)踐一步到位。 跳躍表 跳躍列表是對(duì)...

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

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

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<