computer science

6

Modify the bfs.java program (Listing A) to find the minimum spanning tree using a breadth-first search, rather than the depth-first search shown in

mst.java (Listing B). In main(), create a graph with 9 vertices and 12 edges,

and find its minimum spanning tree.

Listing A: The bfs.java Program

// bfs.java

// demonstrates breadth-first search

// to run this program: C>java BFSApp

////////////////////////////////////////////////////////////////

class Queue

{

private final int SIZE = 20;

private int[] queArray;

private int front;

private int rear;

// -------------------------------------------------------------

public Queue() // constructor

{

queArray = new int[SIZE];

front = 0;

rear = -1;

}

// -------------------------------------------------------------

public void insert(int j) // put item at rear of queue

{

if(rear == SIZE-1)

rear = -1;

queArray[++rear] = j;

}

// -------------------------------------------------------------

public int remove() // take item from front of queue

{

int temp = queArray[front++];

if(front == SIZE)

front = 0;

return temp;

}

// -------------------------------------------------------------

public boolean isEmpty() // true if queue is empty

{

return ( rear+1==front || (front+SIZE-1==rear) );

}

// -------------------------------------------------------------

} // end class Queue

////////////////////////////////////////////////////////////////

class Vertex

{

public char label; // label (e.g. ‘A’)

public boolean wasVisited;

// -------------------------------------------------------------

public Vertex(char lab) // constructor

{

label = lab;

wasVisited = false;

}

// -------------------------------------------------------------

} // end class Vertex

////////////////////////////////////////////////////////////////

class Graph

{

private final int MAX_VERTS = 20;

private Vertex vertexList[]; // list of vertices

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

private int nVerts; // current number of vertices

private Queue theQueue;

// ------------------

public Graph() // constructor

{

vertexList = new Vertex[MAX_VERTS];

// adjacency matrix

adjMat = new int[MAX_VERTS][MAX_VERTS];

nVerts = 0;

for(int j=0; j<MAX_VERTS; j++) // set adjacency

for(int k=0; k<MAX_VERTS; k++) // matrix to 0

adjMat[j][k] = 0;

theQueue = new Queue();

} // end constructor

// -------------------------------------------------------------

public void addVertex(char lab)

{

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

}

// -------------------------------------------------------------

public void addEdge(int start, int end)

{

adjMat[start][end] = 1;

adjMat[end][start] = 1;

}

// -------------------------------------------------------------

public void displayVertex(int v)

{

System.out.print(vertexList[v].label);

}

// -------------------------------------------------------------

public void bfs() // breadth-first search

{ // begin at vertex 0

vertexList[0].wasVisited = true; // mark it

displayVertex(0); // display it

theQueue.insert(0); // insert at tail

int v2;

while( !theQueue.isEmpty() ) // until queue empty,

{

int v1 = theQueue.remove(); // remove vertex at head

// until it has no unvisited neighbors

while( (v2=getAdjUnvisitedVertex(v1)) != -1 )

{ // get one,

vertexList[v2].wasVisited = true; // mark it

displayVertex(v2); // display it

theQueue.insert(v2); // insert it

} // end while

} // end while(queue not empty)

// queue is empty, so we’re done

for(int j=0; j<nVerts; j++) // reset flags

vertexList[j].wasVisited = false;

} // end bfs()

// -------------------------------------------------------------

// returns an unvisited vertex adj to v

public int getAdjUnvisitedVertex(int v)

{

for(int j=0; j<nVerts; j++)

if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)

return j;

return -1;

} // end getAdjUnvisitedVertex()

// -------------------------------------------------------------

} // end class Graph

////////////////////////////////////////////////////////////////

class BFSApp

{

public static void main(String[] args)

{

Graph theGraph = new Graph();

theGraph.addVertex(‘A’); // 0 (start for dfs)

theGraph.addVertex(‘B’); // 1

theGraph.addVertex(‘C’); // 2

theGraph.addVertex(‘D’); // 3

theGraph.addVertex(‘E’); // 4

theGraph.addEdge(0, 1); // AB

theGraph.addEdge(1, 2); // BC

theGraph.addEdge(0, 3); // AD

theGraph.addEdge(3, 4); // DE

System.out.print(“Visits: “);

theGraph.bfs(); // breadth-first search

System.out.println();

} // end main()

} // end class BFSApp

////////////////////////////////////////////////////////////////

Listing B: The mst.java program

// mst.java

// demonstrates minimum spanning tree

// to run this program: C>java MSTApp

////////////////////////////////////////////////////////////////

class StackX

{

private final int SIZE = 20;

private int[] st;

private int top;

// -------------------------------------------------------------

public StackX() // constructor

{

st = new int[SIZE]; // make array

top = -1;

}

// -------------------------------------------------------------

public void push(int j) // put item on stack

{ st[++top] = j; }

// -------------------------------------------------------------

public int pop() // take item off stack

{ return st[top--]; }

// -------------------------------------------------------------

public int peek() // peek at top of stack

{ return st[top]; }

// -------------------------------------------------------------

public boolean isEmpty() // true if nothing on stack

{ return (top == -1); }

// -------------------------------------------------------------

} // end class StackX

////////////////////////////////////////////////////////////////

class Vertex

{

public char label; // label (e.g. ‘A’)

public boolean wasVisited;

// -------------------------------------------------------------

public Vertex(char lab) // constructor

{

label = lab;

wasVisited = false;

}

// -------------------------------------------------------------

} // end class Vertex

////////////////////////////////////////////////////////////////

class Graph

{

private final int MAX_VERTS = 20;

private Vertex vertexList[]; // list of vertices

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

private int nVerts; // current number of vertices

private StackX theStack;

// -------------------------------------------------------------

public Graph() // constructor

{

vertexList = new Vertex[MAX_VERTS];

// adjacency matrix

adjMat = new int[MAX_VERTS][MAX_VERTS];

nVerts = 0;

for(int j=0; j<MAX_VERTS; j++) // set adjacency

for(int k=0; k<MAX_VERTS; k++) // matrix to 0

adjMat[j][k] = 0;

theStack = new StackX();

} // end constructor

// -------------------------------------------------------------

public void addVertex(char lab)

{

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

}

// -------------------------------------------------------------

public void addEdge(int start, int end)

{

adjMat[start][end] = 1;

adjMat[end][start] = 1;

}

// -------------------------------------------------------------

public void displayVertex(int v)

{

System.out.print(vertexList[v].label);

}

// -------------------------------------------------------------

public void mst() // minimum spanning tree (depth first)

{ // start at 0

vertexList[0].wasVisited = true; // mark it

theStack.push(0); // push it

while( !theStack.isEmpty() ) // until stack empty

{ // get stack top

int currentVertex = theStack.peek();

// get next unvisited neighbor

int v = getAdjUnvisitedVertex(currentVertex);

if(v == -1) // if no more neighbors

theStack.pop(); // pop it away

else // got a neighbor

{

vertexList[v].wasVisited = true; // mark it

theStack.push(v); // push it

// display edge

displayVertex(currentVertex); // from currentV

displayVertex(v); // to v

System.out.print(“ “);

}

} // end while(stack not empty)

// stack is empty, so we’re done

for(int j=0; j<nVerts; j++) // reset flags

vertexList[j].wasVisited = false;

} // end tree

// -------------------------------------------------------------

// returns an unvisited vertex adj to v

public int getAdjUnvisitedVertex(int v)

{

for(int j=0; j<nVerts; j++)

if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)

return j;

return -1;

} // end getAdjUnvisitedVertex()

// -------------------------------------------------------------

} // end class Graph

////////////////////////////////////////////////////////////////

class MSTApp

{

public static void main(String[] args)

{

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.addEdge(0, 1); // AB

theGraph.addEdge(0, 2); // AC

theGraph.addEdge(0, 3); // AD

theGraph.addEdge(0, 4); // AE

theGraph.addEdge(1, 2); // BC

theGraph.addEdge(1, 3); // BD

theGraph.addEdge(1, 4); // BE

theGraph.addEdge(2, 3); // CD

theGraph.addEdge(2, 4); // CE

theGraph.addEdge(3, 4); // DE

System.out.print(“Minimum spanning tree: “);

theGraph.mst(); // minimum spanning tree

System.out.println();

} // end main()

} // end class MSTApp

////////////////////////////////////////////////////////////////