频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
复杂网络(2)图论的基本理论 最小生成树问题
2016-12-20 09:28:00         来源:锦小年的博客  
收藏   我要投稿

连通且不含圈的无向图称为树。树中度为1的节点称为树叶,度大于1的节点称为分支点。若图G=(V,E)的生成子图是一棵树,则称该树为图G的生成树,也称支撑树,简称为图G的树。图G中属于生成树的边称为树枝。

连通图G=(V,E),每条边上有非负权L(e)。一棵树上所有树枝上权的总和,称为这个生成树的权。具有最小权的生成树称为最小生成树,也称最小支撑树,简称最小树。

许多网络问题都可以归结为最小树问题,例如:交通系统,通信系统,局域网系统等等。
最小生成树的算法:

世界杯外围投注官网

普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现;并在1957年由美国计算机科学家罗伯特·普里姆发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

给定连通赋权图G=(V,E,W),其中W为邻接矩阵,构造它的最小生成树。设置两个集合P和Q,其中P用于存放G的最小生成树的节点,集合Q存放G的最小生成树的边。令集合P的初值为P={V1}(假设构造最小生成树时从节点V1出发),集合Q的初值Q=空集。Prim算法的思想是,从所有p属于P,v属于V-P的边中,选取具有最小权值得边pv,将节点v加入集合P中,将边pv加入集合Q中,如此不断的重复,直到P=V时,最小生成树构造完毕,这时集合Q包含了最小生成树的所有边。

1 算法简单描述

1).输入:一个加权连通图,其中顶点集合为V,边集合为E;
2).初始化:P = {x},其中x为集合V中的任一节点(起始点),Q = {},为空;
3).重复下列操作,直到P = V:
a.在集合E中选取权值最小的边

2 算法的图例描述

3 简单证明prim算法

反证法:假设prim生成的不是最小生成树

1).设prim生成的树为G0 2).假设存在Gmin使得cost(Gmin)

4 prim算法的python实现

&世界杯外围投注官网39;&世界杯外围投注官网39;&世界杯外围投注官网39;
世界杯外围投注官网file:py_prim.py
世界杯外围投注官网最小生成树 prim算法的python实现
&世界杯外围投注官网39;&世界杯外围投注官网39;&世界杯外围投注官网39;
debug = 0
MAX_NUM = 10000
v_num = 6
grapharr = [[0, 6, 1, 5, MAX_NUM, MAX_NUM],
            [6, 0, 5, MAX_NUM, 3, MAX_NUM],
            [1, 5, 0, 5, 5, 4],
            [5, MAX_NUM, 5, 0, MAX_NUM, 2],
            [MAX_NUM, 3, 6, MAX_NUM, 0, 6],
            [MAX_NUM, MAX_NUM, 4, 2, 6, 0],
            ]
世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网
世界杯外围投注官网 U放已经匹配好的顶点:
U = []
世界杯外围投注官网 V初始化为所有顶点的集合:
V = []
世界杯外围投注官网 T放各个边:
T = []

def init():
    if (debug):
        print("grapharr=", end="")
        print(grapharr)
    i = 0
    while i < v_num:
        V.append(i + 1)
        i = i + 1

def prim_start_vertex(start):
    if (start < 1):
        print("ERROR:start=", start)
        print("ERROR:change start to 1 by default!")
        start = 1
    U.append(start)
    del V[start - 1]

def list_sort(l):
    if (len(l) < 1):
        print("ERROR:len of l =", len(l))
        exit
    index = 0
    i = 0
    min_val = l[0]
    while i < len(l):
        if min_val > l[i]:
            min_val = l[i]
            index = i
        i = i + 1
    if (debug):
        print("[list_sort]:l=", l, ";index=", index)
    return index

def min_wui():
    m = MAX_NUM
    close_edge = {&世界杯外围投注官网39;u&世界杯外围投注官网39;: -1, &世界杯外围投注官网39;v&世界杯外围投注官网39;: -1}
    edge_list = []
    vertex_list = []
    i = 0
    j = 0
    世界杯外围投注官网 算出U和V之间所有边的长度:
    lu = len(U)
    lv = len(V)
    if (debug):
        print("世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网entry min_wui世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网")
        print("lu=", lu, ";lv=", lv)
    while i < len(U):
        while j < len(V):
            if (debug):
                print("i=", i, ";j=", j)
                print("U[i]=", U[i], ";V[j]=", V[j])
            temp = grapharr[U[i] - 1][V[j] - 1]
            if (temp > 0):
                if (temp < MAX_NUM):
                    close_edge = {&世界杯外围投注官网39;u&世界杯外围投注官网39;: U[i], &世界杯外围投注官网39;v&世界杯外围投注官网39;: V[j]}
                if (debug):
                    print("close_edge=", close_edge)
                vertex_list.append(close_edge)
                edge_list.append(temp)
            j = j + 1
        世界杯外围投注官网 for i:
        i = i + 1
        j = 0
    世界杯外围投注官网 end of :for while i
    if (debug):
        print("vertex_list=", vertex_list)
        print("edge_list=", edge_list)
    min_index = list_sort(edge_list)
    close_edge = vertex_list[min_index]
    U.append(close_edge[&世界杯外围投注官网39;v&世界杯外围投注官网39;])
    del V[V.index(close_edge[&世界杯外围投注官网39;v&世界杯外围投注官网39;])]
    if (debug):
        print("U=", U)
        print("V=", V)
    return close_edge

def py_prim(start):
    init()
    prim_start_vertex(start)
    print("init values:")
    print("U=", U)
    print("V=", V)
    print("T=", T)
    while (len(U) != v_num):
        if (debug):
            print("len(U)=", len(U))
        our_edge = min_wui()
        T.append(our_edge)
    print("========RESULT============")
    print("U=", U)
    print("V=", V)
    print("T=", T)

世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网世界杯外围投注官网
if (__name__ == "__main__"):
    世界杯外围投注官网 开始主程序:
    debug = 0
    py_prim(1)

调试结果:
init values:
U= [1]
V= [2, 3, 4, 5, 6]
T= []
========RESULT============
U= [1, 3, 6, 4, 2, 5]
V= []
T= [{&世界杯外围投注官网39;v&世界杯外围投注官网39;: 3, &世界杯外围投注官网39;u&世界杯外围投注官网39;: 1}, {&世界杯外围投注官网39;v&世界杯外围投注官网39;: 6, &世界杯外围投注官网39;u&世界杯外围投注官网39;: 3}, {&世界杯外围投注官网39;v&世界杯外围投注官网39;: 4, &世界杯外围投注官网39;u&世界杯外围投注官网39;: 6}, {&世界杯外围投注官网39;v&世界杯外围投注官网39;: 2, &世界杯外围投注官网39;u&世界杯外围投注官网39;: 3}, {&世界杯外围投注官网39;v&世界杯外围投注官网39;: 5, &世界杯外围投注官网39;u&世界杯外围投注官网39;: 2}]

二 kruskal算法

Kruskal算法是一种用来寻找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。

1 kruskal算法的精髓在于:每次选取一条边,该边同时满足:

1、在当前未选边中权值最小;
2、与已选边不构成回路。直到选取n-1条表是算法结束。找到MST活判断不存在MST。

2.算法简单描述

1).记Graph中有v个顶点,e个边
2).新建图Graphnew,Graphnew中拥有原图中相同的e个顶点,但没有边
3).将原图Graph中所有e个边按权值从小到大排序
4).循环:从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中
if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中
添加这条边到图Graphnew中

3 图片描述

3.简单证明Kruskal算法
对图的顶点数n做归纳,证明Kruskal算法对任意n阶图适用。
归纳基础:
n=1,显然能够找到最小生成树。
归纳过程:
假设Kruskal算法对n≤k阶图适用,那么,在k+1阶图G中,我们把最短边的两个端点a和b做一个合并操作,即把u与v合为一个点v’,把原来接在u和v的边都接到v’上去,这样就能够得到一个k阶图G’(u,v的合并是k+1少一条边),G’最小生成树T’可以用Kruskal算法得到。
我们证明T’+{

4.世界杯外围投注网站算法实现

from pylab import *
INFINITY = 65535                        世界杯外围投注官网代表无穷大
vexs = array([[0,10,INFINITY,INFINITY,INFINITY,11,INFINITY,INFINITY,INFINITY],世界杯外围投注官网邻接矩阵
        [10,0,18,INFINITY,INFINITY,INFINITY,16,INFINITY,12],
        [INFINITY,18,0,22,INFINITY,INFINITY,INFINITY,INFINITY,8],
        [INFINITY,INFINITY,22,0,20,INFINITY,INFINITY,16,21],
        [INFINITY,INFINITY,INFINITY,20,0,26,INFINITY,7,INFINITY],
        [11,INFINITY,INFINITY,INFINITY,26,0,17,INFINITY,INFINITY],
        [INFINITY,16,INFINITY,24,INFINITY,17,0,19,INFINITY],
        [INFINITY,INFINITY,INFINITY,16,7,INFINITY,19,0,INFINITY],
        [INFINITY,12,8,21,INFINITY,INFINITY,INFINITY,INFINITY,0]])
lengthVex = len(vexs)                   世界杯外围投注官网邻接矩阵大小
beginEdge = []
endEdge = []
weight = []
group = []
for i in arange(lengthVex):             世界杯外围投注官网生成边集数组
    group.append([i])
    for j in arange(i+1,lengthVex):
        if(vexs[i, j]>0 and vexs[i, j]

5 时间复杂度:elog2e e为图中的边数

点击复制链接 与好友分享!回本站首页
上一篇:一组整数中找出3元素组合
下一篇:Hadoop配置文件
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑--致力于做实用的IT技术学习网站