Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4242076
  • 博文数量: 176
  • 博客积分: 10059
  • 博客等级: 上将
  • 技术积分: 4681
  • 用 户 组: 普通用户
  • 注册时间: 2006-03-24 12:27
文章分类

全部博文(176)

文章存档

2012年(1)

2011年(4)

2010年(14)

2009年(71)

2008年(103)

分类: Java

2008-04-13 02:16:10

对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,记作:
   
 这里:
     TE表示T的边集
     w(u,v)表示边(u,v)的权。
     权最小的生成树称为G的最小生成树(Minimum Spannirng Tree)。最小生成树可简记为MST。

本文给出带权图的最小生成树的Prim算法。该算法描述如下:
 Prim算法的基本思想是:
  (1) 在图G=(V, E) (V表示顶点 ,E表示边)中,从集合V中任取一个顶点(例如取顶点v0)放入集合 U中,这时 U={v0},集合T(E)为空。
  (2) 从v0出发寻找与U中顶点相邻(另一顶点在V中)权值最小的边的另一顶点v1,并使v1加入U。即U={v0,v1 },同时将该边加入集合T(E)中。
  (3) 重复(2),直到U = V为止。
  这时T(E)中有n-1条边,T = (U, T(E))就是一棵最小生成树。

在算法执行过程中有三中类型的顶点:
类型1:已经扫描,且已经确定为MST中的顶点
类型2:即将扫描的顶点,这些顶点到与MST树中顶点相连,且权重已经知道了
类型3:还未被扫描,却这些顶点与MST不相邻

在具体Java语言实现时,用一个优先级队列存储带权的边,每次扫描一个顶点,就将该顶点加入到MST树种,同时将与该顶点相邻的但还不在队列中的边加入到队列中来(即上述类型2与类型1之间相连的边),同时保证类型2的顶点到MST树只有一条边在队列中,且为权重最小的边。

更具体的看代码实现吧:

package zieckey.datastructure.study.graph;

import zieckey.datastructure.study.queue.PriorityQueue;

/**
 * 无向有权图
 *
 * @author zieckey
 */


public class WeightedGraph
{
    private final int        MAX_VERTS    = 20;
    private final int        INFINITY    = 1000000;
    private Vertex[]        vertexList;            // list of vertices

    private int[][]            adjMat;                // adjacency matrix

    private int                nVerts;                // current number of vertices

    private int                currentVert;
    private PriorityQueue    thePQ;
    private int                nTree;                    // number of verteces in tree


    /**
     * 默认构造函数 初始化邻接矩阵
     */

    public WeightedGraph( )
    {
        vertexList = new Vertex[MAX_VERTS];
        // 图的邻接矩阵adjacency matrix

        adjMat = new int[MAX_VERTS][MAX_VERTS];
        thePQ = new PriorityQueue();
        
        nVerts = 0;
        for ( int j = 0; j < MAX_VERTS; j++ )
        {
            // set adjacency

            for ( int k = 0; k < MAX_VERTS; k++ )
            {
                adjMat[j][k] = INFINITY;
            }
        }
    }
    
    /**
     * 带权图的最小生成树算法。采用Prim算法。
     *
     *  对于网络,其生成树中的边也带权,将生成树各边的权值总和称为生成树的权,
     * 并将权值最小的生成树称为最小生成树(Minimun Spanning Tree),简称为MST。
     *
     *  Prim算法的基本思想是:
     *      (1) 在图G=(V, E) (V表示顶点 ,E表示边)中,从集合V中任取一个顶点(例如取顶点v0)放入集合 U中,
     *             这时 U={v0},集合T(E)为空。
     *         (2) 从v0出发寻找与U中顶点相邻(另一顶点在V中)权值最小的边的另一顶点v1,
     *            并使v1加入U。即U={v0,v1 },同时将该边加入集合T(E)中。
     *          (3) 重复(2),直到U = V为止。
     *  这时T(E)中有n-1条边,T = (U, T(E))就是一棵最小生成树。
     */

    public void buildMinimumSpanningTreeOfWeightedGraph()
    {
        currentVert = 0; // 从节点 0 开始

        
        /**
         * 当所有的点都在MST树中时,停止循环
         * 每循环一次,就添加一条边和一个顶点到MST树中
         */

        while ( nTree < nVerts )
        {
            //将当前扫描的节点放入MST树中

            vertexList[currentVert].isInTree = true;
            
            nTree++;
            
            /**
             *    把与当前扫描的节点currentVert相邻的边都插入到优先级队列中。
             * 这里保证了所有与MST树(中所有点)相邻的边都插入近来了。
             * 又因为,插入函数内部的控制,使得任何一个MST树的点最多只有一条边与MST树相连。
             * 该边为该点到MST树权重最小的那条边
             */

            for ( int j = 0; j < nVerts; j++ ) // for each vertex,

            {
                if ( j == currentVert ) // skip if it's itself

                {
                    continue;
                }
                if ( vertexList[j].isInTree ) // skip if in the tree

                {
                    continue;
                }
                int distance = adjMat[currentVert][j];
                if ( distance == INFINITY ) // skip if no edge

                {
                    continue;
                }
                putInPQ( j, distance ); // put it in PQ (maybe)

            }
            
            if ( thePQ.size() == 0 ) // no vertices in PQ?

            {
                System.out.println( " GRAPH NOT CONNECTED" );
                return;
            }
            
            /**
             * 每循环一次,就添加一条边和一个顶点到MST树中
             * 移出优先级队列中权重最小的边,添加到MST树中
             */

            Edge theEdge = thePQ.removeMin();
            int sourceVert = theEdge.srcVert;
            currentVert = theEdge.destVert;
            // display edge from source to current

            System.out.print( vertexList[sourceVert].label );
            System.out.print( vertexList[currentVert].label );
            System.out.print( " " );
        }
        
        // 算法结束

        for(int j=0; j<nVerts; j++)
        {
            vertexList[j].isInTree = false;
        }
    }

    /**
     * 添加一个节点
     *
     * @param lab
     */

    public void addVertex( char lab ) // argument is label

    {
        vertexList[nVerts++ ] = new Vertex( lab );
    }

    /**
     * 添加一条边
     *
     * @param start
     * 起始点
     * @param end
     * 终点
     */

    public void addEdge( int start, int end, int weight )
    {
        adjMat[start][end] = weight;
        adjMat[end][start] = weight;
    }
    
    /**
     * 显示一个节点
     *
     * @param v
     */

    public void displayVertex( int v )
    {
        System.out.print( vertexList[v].label );
    }
    
    /**
     *
     * @param newVert 一个新的节点,由currentVert指向newVert
     * @param newDist currentVert与newVert之间的权重(距离)    
     */

    public void putInPQ(int newVertex, int newDistence)
    {
        int tempIndex = thePQ.find( newVertex );
        if ( -1 != tempIndex )//找到尾为newVertex的边

        {
            Edge tempEdge = thePQ.peekN( tempIndex );
            if ( tempEdge.distance > newDistence )
            {
                thePQ.removeN( tempIndex );
                Edge newEdge = new Edge( currentVert, newVertex, newDistence );
                thePQ.insert( newEdge );
            }//else, 没有操作

            
        }else //没有找到这样的边,直接插入

        {
            Edge newEdge = new Edge( currentVert, newVertex, newDistence );
            thePQ.insert( newEdge );
        }
    }
}

另外:

package zieckey.datastructure.study.graph;

/**
 * 带权重的边
 * @author zieckey
 *
 */

public class Edge
{
    public int    srcVert;    // index of a vertex starting edge

    public int    destVert;    // index of a vertex ending edge

    public int    distance;    // distance from src to dest


    public Edge( int sv, int dv, int d ) // constructor

    {
        srcVert = sv;
        destVert = dv;
        distance = d;
    }
} // end class Edge



package zieckey.datastructure.study.graph;

/**
 *
 * 图中的(节)点。
 *
 * @author zieckey
 *
 */

class Vertex
{
    public char        label;        // label (e.g. 'A')

    public boolean    wasVisited;
    public boolean    isInTree;

    public Vertex( char lab ) // constructor

    {
        label = lab;
        wasVisited = false;
        isInTree = false;
    }

} // end class Vertex

至于优先级队列,请看:http://blog.chinaunix.net/u/16292/showart_529106.html。

阅读(10486) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~

zieckey2009-03-23 20:44:50

文中最后提到了“至于优先级队列,请看:http://blog.chinaunix.net/u/16292/showart_529106.html

chinaunix网友2009-03-21 14:07:33

太不专业了,抄袭别人的东西最起码要抄袭正确啊,你优先级队列里面 thePQ.find(int a ) 这个方法都没有