最小生成树

前言

在电子电路设计中,我们常常需要将多个组件的针脚连接在一起,要连接n个针脚,我们可以使用n-1根连线。很显然,我们希望所使用的连线最短。

可以将上述布线问题用一个连通无向图 G = {V, E} 来表示,V是针脚的集合,E是针脚之间的可能连接,并且为每条边 {u , v}属于E,我们为其赋权重 w 作为连接针脚u和v的代价。我们希望找到一个无环子集T,既能连接所有的针脚,又有最小代价。

因为T是无环子集,并且连通所有结点,因此T必然是一棵树,我们称这样的树是图的最小生成树。

求解最小生成树有两种方法,Kruskal算法和Prim算法。

本文中使用的图

Kruskal算法

Kruskal算法,在所有连接森林中两棵不同树的边里边,找到权重最小的边加入到森林。

简单地说,Kruskal算法将边排序,根据贪心算法思维,选择最短边。但最小生成树的结果要求是无环的,且每个顶点都需要包括,如何确保这个结果呢?

将图中的每个顶点当成一棵单独的树,如果选择的最短边为{u、v},森林中这两棵树并未交集,则合并这两棵树到森林中。直到森林中包含所有的结点。

算法导论上的伪码如下:

Kruskal算法中的难点就在于确保无环且包含所有结点,并且是连通图。

将每个结点都看成一棵树,如果选中的边两顶点位于不同的树中,则合并这两棵树加入森林,这就间接使两个顶点相连了。如果两个已经连通的顶点已经被加入森林中,那么就不符合条件而不会被重复加入,因此也会是无环的。

/*
 * 将边按权重从小到大排列
 * 如果边的两个顶点在不同树中则将这两棵树合并,且加入森林
 * 在森林中的顶点则是连通的,已连通的顶点在森林中,也不会重复添加边,达到无环要求
 */
public void kruskal(){
    MatrixGraph graph = initUndigraph();
    MatrixEdge[] array = getEdges(graph, null);
    //为边排序
    sort(array, 0, array.length-1);
    //构造森林,森林中的元素就是一棵棵树,初始树中只包含一个顶点
    ArrayList<HashSet<Vertex>> list = new ArrayList<>();
    for (int i = 0; i < graph.mList.size(); i++) {
        HashSet<Vertex> set = new HashSet<>();
        set.add(graph.mList.get(i));
        list.add(set);
    }
    MatrixEdge edge = null;
    for (int i = 0; i < array.length; i++) {
        edge = array[i];
        Vertex v1 = edge.v1;
        Vertex v2 = edge.v2;
        int count1 = -1;
        int count2 = -1;
        for (int j = 0; j < list.size(); j++) {
            HashSet<Vertex> set = list.get(j);
            //找到顶点在森林中的位置
            if (set.contains(v1)) {
                count1 = j;
            }
            if (set.contains(v2)) {
                count2 = j;
            }
        }
        if (count1 == -1 || count2 == -1) {
            return;
        }else {
            if (count1 != count2) {
                //如果顶点分别在不同的树中,则合并这两棵树并且删除之前的旧树
                //因为会合并树,所以已经连通的顶点就会在合并的树中,在同一棵树中
                //count1等于count2,所以能保证无环
                //最终森林中只有一棵树,且包含全部顶点
                HashSet<Vertex> set1 = list.get(count1);
                HashSet<Vertex> set2 = list.get(count2);
                set1.addAll(set2);
                if (count1 < count2) {
                    list.remove(count1);
                    list.remove(count2-1);
                }else {
                    list.remove(count2);
                    list.remove(count1-1);
                }
                list.add(set1);
                System.out.println(edge);
            }
        }
    }
}

值得一提的是,图中两种存储方式,矩阵和链表,Kruskal算法需要对所有边排序,而邻接链表中直观获取所有边比较难,所以需要用邻接矩阵存储图。

Prim算法

Prim算法,从图中任意挑选出一个顶点放入集合list中,在list的所有顶点中选出边最短的一条边,并且将边的另一顶点也加入list中,如此重复到所有顶点都已加入到list中。

算法步骤:

  • 输入:一个加权连通图,其中顶点集合为V,边集合为E
  • 初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;
  • 重复下列操作,直到Vnew = V:
    a: 在集合E中选取权值最小的边<u, v>,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
    b: 将v加入集合Vnew中,将<u, v>边加入集合Enew中
  • 输出:使用集合Vnew和Enew来描述所得到的最小生成树。

prim算法是比kruskal更简单一点。因为prim算法需要计算以某顶点为起点的最小边,所以使用邻接链表存储图更合适。

/*
 * 构造新结点list,先从图中选中任意结点加入
 * 不断遍历list中的结点,选择与结点相关的最短边,且将边的另一端加入到list中
 * 选择的最短边的另一个结点之前不能在list中
 * 最后list与图中顶点表相同则结束整个过程
 */
public void prim(){
    Graph graph = initUndigraph();
    Vertex start = graph.mList.get(0);
    //构建新list
    List<Vertex> oldList = graph.mList;
    List<Vertex> newList = new ArrayList<Vertex>();
    newList.add(start);
    Vertex v = null;
    Arc vArc = null;
    //最短边的权重、对应的弧、对应的弧起点
    int vMinW = Integer.MAX_VALUE;
    Arc vMinArc = null;
    Vertex vMinVertex = null;
    while (newList.size() < oldList.size()) {
        //查找出新list中最短边
        for (int i = 0; i < newList.size(); i++) {
            v = newList.get(i);
            vArc = v.firstArc;
            while (vArc != null) {
                if (vMinW > vArc.weight && !newList.contains(vArc.vertex)) {
                    vMinW = vArc.weight;
                    vMinArc = vArc;
                    vMinVertex = v;
                }
                vArc = vArc.next;
            }
        }
        //输出结果
        if (vMinArc != null && vMinArc.vertex != null && !newList.contains(vMinArc.vertex)) {
            System.out.println(vMinVertex.info + "    " + vMinArc.weight + "    " + vMinArc.vertex.info);
            newList.add(vMinArc.vertex);
            vMinW = Integer.MAX_VALUE;
        }
    }
}

所有代码均上传至本人的github,欢迎访问。从本文来看,图的不同存储方式也能带来不同的便利。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,163评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,301评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,089评论 0 352
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,093评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,110评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,079评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,005评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,840评论 0 273
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,278评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,497评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,667评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,394评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,980评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,628评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,649评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,548评论 2 352

推荐阅读更多精彩内容