Suppose we want to install a cable television line that
connects six towns in the mythical country of Magnaguena. Five links will
connect the six cities, but which five links should they be? The cost of
connecting each pair of cities varies, so we must pick the route carefully to
minimize the overall cost.
Minimum spanning tree
The algorithm is carried out in the while loop, which
terminates when all vertices are in the tree. Within this loop the following
activities take place:
1. The current vertex (Row) is placed in the tree.
2. The edges adjacent to this vertex are placed in the
priority queue (if appropriate).
3. The edge with the minimum weight is removed from the
priority queue. The destination vertex of this edge becomes the current vertex (Row).
Let’s look at these steps in more detail. In step 1, the row
is placed in the tree by marking its isInTree field.
In step 2, the edges adjacent to this vertex are considered
for insertion in the priority queue. The edges are examined by scanning across
the row in the adjacency matrix. An edge is placed in the queue unless one of these
conditions is true:
• The source and destination vertices are the same.
• The destination vertex is in the tree.
• There is no edge to this destination.
If none of these conditions are true, the putInPQ() method
is called to put the edge in the priority queue. Actually, this routine doesn’t
always put the edge in the queue either, as we’ll see in a moment.
In step 3, the edge with the minimum weight is removed from
the priority queue. This edge and its destination vertex are added to the tree,
and the source vertex (row) and destination vertex are displayed.
At the end of mstw(), the vertices are removed from the tree
by resetting their isInTree variables. That isn’t strictly necessary in this
program because only one tree is created from the data. However, it’s good
housekeeping to restore the data to its original form when you finish with it.
As we noted, the priority queue should contain only one edge
with a given destination vertex. The putInPQ() method makes sure this is true.
It calls the findByDestination() method of the PriorityQ class, which has been
doctored to find the edge with a specified destination vertex. If there is no
such vertex, and findByDestination() therefore returns –1, then putInPQ()
simply inserts the edge into the priority queue. However, if such an edge does
exist, putInPQ() checks to see whether the existing edge or the new proposed edge
has the lower weight. If it’s the old edge, no change is necessary. If the new
one has a lower weight, the old edge is removed from the queue and the new one
is installed.
//****************************************************************
//* Copyright (c) 2015. All Rights Reserved.
//****************************************************************
package com.ds.weightedgraph;
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(final
int sv, final int dv, final int d) // constructor
{
this.srcVert =
sv;
this.destVert
= dv;
this.distance
= d;
}
}
//****************************************************************
//* Copyright (c) 2015. All Rights Reserved.
//****************************************************************
package com.ds.weightedgraph;
public class Vertex {
public char label;
// label (e.g. ‘A’)
public boolean
isInTree;
public
Vertex(final char lab) // constructor
{
this.label =
lab;
this.isInTree
= false;
}
}
//****************************************************************
//* Copyright (c) 2015. All Rights Reserved.
//****************************************************************
package com.ds.weightedgraph;
public class PriorityQ {
// array in sorted
order, from max at 0 to min at size-1
private final int
SIZE = 20;
private Edge[]
queArray;
private int size;
public PriorityQ()
// constructor
{
this.queArray
= new Edge[this.SIZE];
this.size = 0;
}
public void
insert(final Edge item) // insert item in sorted order
{
int j;
for (j = 0; j
< this.size; j++)
// find
place to insert
if
(item.distance >= this.queArray[j].distance)
break;
for (int k =
this.size - 1; k >= j; k--)
// move
items up
this.queArray[k + 1] = this.queArray[k];
this.queArray[j] = item; // insert item
this.size++;
}
public Edge
removeMin() // remove minimum item
{
this.size =
this.size - 1;
final Edge temp = this.queArray[this.size];
this.queArray[this.size] = null;
return temp;
}
public void
removeN(final int n) // remove item at n
{
for (int j =
n; j < this.size - 1; j++)
// move
items down
this.queArray[j] = this.queArray[j + 1];
this.size--;
}
public Edge
peekMin() // peek at minimum item
{
return
this.queArray[this.size - 1];
}
public int size()
// return number of items
{
return
this.size;
}
public boolean
isEmpty() // true if queue is empty
{
return
(this.size == 0);
}
//
-------------------------------------------------------------
public Edge
peekN(final int n) // peek at item n
{
return
this.queArray[n];
}
public int
findByDestination(final int findDex) // find item with specified
{ // destVert
value
for (int j =
0; j < this.size; j++)
if
(this.queArray[j].destVert == findDex)
return j;
return -1;
}
}
//****************************************************************
//* Copyright (c) 2015. All Rights Reserved.
//****************************************************************
package com.ds.weightedgraph;
public class Graph {
private final int MAX_VERTS = 6;
private final int INFINITY = 1000000;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int totalVerts; // current number of vertices
private PriorityQ thePQ;
public Graph() // constructor
{
this.vertexList = new Vertex[this.MAX_VERTS];
// adjacency matrix
this.adjMat = new int[this.MAX_VERTS][this.MAX_VERTS];
this.totalVerts = 0;
for (int j = 0; j < this.MAX_VERTS; j++)
// set adjacency
for (int k = 0; k < this.MAX_VERTS; k++)
// matrix to 0
this.adjMat[j][k] = this.INFINITY;
this.thePQ = new PriorityQ();
}
public void addVertex(final char lab) {
this.vertexList[this.totalVerts++] = new Vertex(lab);
}
public void addEdge(final int start, final int end, final int weight) {
this.adjMat[start][end] = weight;
this.adjMat[end][start] = weight;
}
public void displayVertex(final int v) {
System.out.print(this.vertexList[v].label);
}
public void mstw() {
int row = 0; // start at 0
int startingVertsPos = 0; // number of verts in tree
while (startingVertsPos < this.totalVerts - 1) // while not all verts in
// tree
{ // put currentVert in tree
this.vertexList[row].isInTree = true;
startingVertsPos++;
// insert edges adjacent to currentVert into PQ
for (int column = 0; column < this.totalVerts; column++) // for each vertex, for a
// particular row column
// wise loop
{
if (column == row) // skip if it’s us
continue;
if (this.vertexList[column].isInTree) // skip if in the tree
continue;
final int distance = this.adjMat[row][column];
if (distance == this.INFINITY) // skip if no edge
continue;
putInPQ(row, column, distance); // put it in PQ (maybe)
}
if (this.thePQ.size() == 0) // no vertices in PQ?
{
System.out.println(" GRAPH NOT CONNECTED");
return;
}
// remove edge with minimum distance, from PQ
final Edge theEdge = this.thePQ.removeMin();
final int sourceVert = theEdge.srcVert;
row = theEdge.destVert;
displayEdgeFromSourceToCurrent(sourceVert, row);
} // end while(not all verts in tree)
// mst is complete
unMarkAllVertex();
} // end mstw
private void displayEdgeFromSourceToCurrent(final int sourceVert,
final int targetVert) {
// display edge from source to current
System.out.print(this.vertexList[sourceVert].label);
System.out.print(this.vertexList[targetVert].label);
System.out.print(" ");
}
private void unMarkAllVertex() {
for (int j = 0; j < this.totalVerts; j++)
// unmark vertices
this.vertexList[j].isInTree = false;
}
public void putInPQ(final int row, final int column,
final int newDist) {
// is there another edge with the same destination vertex?
final int queueIndex = this.thePQ.findByDestination(column);
if (queueIndex != -1) // got edge’s index
{
final Edge tempEdge = this.thePQ.peekN(queueIndex); // get edge
final int oldDist = tempEdge.distance;
if (oldDist > newDist) // if new edge shorter,
{
this.thePQ.removeN(queueIndex); // remove old edge
final Edge theEdge = new Edge(row, column, newDist);
this.thePQ.insert(theEdge); // insert new edge
}
// else no action; just leave the old vertex there
} // end if
else // no edge with same destination vertex
{ // so insert new one
final Edge theEdge = new Edge(row, column, newDist);
this.thePQ.insert(theEdge);
}
} // end putInPQ()
}
//****************************************************************
//* Copyright (c) 2015. All Rights Reserved.
//****************************************************************
package com.ds.weightedgraph;
public class MinimumSpanningWGraph {
public static void main(final String[] args) {
final Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start for mst)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('F'); // 5
theGraph.addEdge(0, 1, 6); // AB 6
theGraph.addEdge(0, 3, 4); // AD 4
theGraph.addEdge(1, 2, 10); // BC 10
theGraph.addEdge(1, 3, 7); // BD 7
theGraph.addEdge(1, 4, 7); // BE 7
theGraph.addEdge(2, 3, 8); // CD 8
theGraph.addEdge(2, 4, 5); // CE 5
theGraph.addEdge(2, 5, 6); // CF 6
theGraph.addEdge(3, 4, 12); // DE 12
theGraph.addEdge(4, 5, 7); // EF 7
System.out.print("Minimum spanning tree: ");
theGraph.mstw(); // minimum spanning tree
System.out.println();
}
}
Kindly provide your valuable feedback in comment box.
No comments:
Post a Comment