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

scq000 發(fā)布于2019-08-21 18:30 / 2655人閱讀

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

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

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

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

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

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

現(xiàn)在問題我們如何去尋找那條只屬于M但不屬于A的邊

邊v的尋找方法
當A為空時，圖G(V,A)是一個有|V|個樹的森林，當A中有n條邊時，n<|V|-1,圖G是一個有|V|-(n+1)個樹的森林，我們需要尋找的邊v的加入會導致圖G中的森林數(shù)目減1邊v是這樣一條邊

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

邊v的權值是所有滿足以上條件中權值最小的

3. Kruskal和Prim 算法

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

4. Kruskal算法

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

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

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

 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é)點所在的那顆樹的根節(jié)點，用于判斷兩個節(jié)點是否在同一顆樹中，即是否相交

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

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

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

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

4.5. Kruskal算法

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

function Kruskal(G, w) {
    let A = []; //A用于存放最小生成數(shù)所包含的邊
    for(let x of G.V) {
        MakeSet(x);
    }
    //對G.E按照邊的權中從小到大排序
    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. 圖，頂點，邊，的數(shù)據(jù)結構

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

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

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

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

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

4.7. 完整代碼及測試

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

//快速排序 數(shù)組a由對象組成 key為排序的參照指標 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) {
        //移動 j
        while (a[j][key] >= benchMark[key] && i < j)
            j--;
        //移動 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;
    }
})();

//體會兩個 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 的層級比 vRoot 的小,將 uRoot 作為 vRoot 前驅節(jié)點
    if (uRoot.rank < vRoot.rank) uRoot.parent = vRoot;
    // 如果 uRoot 的層級比 vRoot 的大,將 vRoot 作為 uRoot 前驅節(jié)點
    else if (uRoot.rank > vRoot.rank) vRoot.parent = uRoot;
    //任選一個作為根節(jié)點
    else {
        vRoot.parent = uRoot;
        uRoot.rank = uRoot.rank + 1;
    }
}

function Kruskal(G) {
    let A = []; //A用于存放最小生成數(shù)所包含的邊
    for(let x of G.V) {
        MakeSet(x);
    }
    //對G.E按照邊的權中從小到大排序
    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; //由頂點發(fā)出的所有邊
    this.id = null; //節(jié)點的唯一標識
    this.data = null; //存放節(jié)點的數(shù)據(jù)
}

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

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

//測試數(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);

GPU云服務器云服務器最小生成樹算法最小代價生成樹算法最小生成樹python算法最小生成樹c++算法

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/90535.html

【程序員必會十大算法】之Kruskal算法

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

freewolf 2021-09-28 09:36 評論0 收藏0
算法（第4版） Chapter 4.3 最小生成樹

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

asoren 2019-08-14 17:16 評論0 收藏0
【圖論】最小生成樹

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

?xiaoxiao, 2019-08-16 12:33 評論0 收藏0
面試算法實踐與國外大廠習題指南

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

genedna 2019-08-14 17:46 評論0 收藏0
數(shù)據(jù)結構與算法——常用高級數(shù)據(jù)結構及其Java實現(xiàn)

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

itvincent 2019-08-15 14:33 評論0 收藏0