对于连通的带权图(连通网)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。
阅读(10426) | 评论(2) | 转发(0) |
