Modify The BFS Java Program Listing To Find The Minimum Span

Modify The Bfsjava Program Listing A To Find The Minimum Spanning

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.

Paper For Above instruction

The task involves transforming an existing BFS implementation in Java to compute the minimum spanning tree (MST) of a graph using a breadth-first search (BFS) approach. While the original BFS code is designed for traversal, the MST in an unweighted graph can be constructed by recording the edges used during the level-by-level traversal, ensuring the minimal edge set connecting all vertices. This paper discusses the methodology, implementation details, and an example setup with a graph of 9 vertices and 12 edges.

Introduction

Graph algorithms play a critical role in computer science, facilitating solutions to problems related to networks, routing, minimum spanning trees, and more. The classic approach to computing a Minimum Spanning Tree (MST) in an undirected, weighted graph is Prim’s or Kruskal’s algorithm. However, in unweighted graphs, where edges have no weight, a breadth-first search (BFS) can be utilized to find a spanning tree that connects all vertices with minimal edges. This approach ensures a minimal number of edges, and when edges are unweighted, BFS-based spanning trees are optimal candidates for MSTs.

Methodology

The existing implementation of BFS in Java constructs a traversal order of vertices starting from a designated source. To modify this for MST construction, during BFS traversal, whenever a new vertex is discovered (meaning, the vertex is being visited for the first time), the edge that led to this vertex is recorded. The collection of such edges upon traversal yields a spanning tree, as BFS naturally explores vertices in layers and connects every vertex to the shortest path (in terms of number of edges) from the starting vertex. As BFS traverses all connected components, applying this process to each connected component yields a minimum spanning forest, and to produce a true MST, the entire graph must be connected or we consider a connected component.

Implementation Details

The primary modifications involve the following:

  • Introduce a data structure to store the edges of the MST, such as a list of pairs indicating source and destination vertices.
  • During BFS, when a new vertex is discovered (via an adjacency that is initially unvisited), record the edge connecting the current vertex to the new vertex.
  • At the end of the BFS traversal, the set of recorded edges forms the minimum spanning tree.
  • Build the graph with 9 vertices and 12 edges, ensuring the graph is connected to produce a MST covering all vertices.

Code Implementation

Starting from the existing BFS code (Listing A), adjustments are applied by adding an edge recording mechanism. The implementation includes initializing a graph with 9 vertices and 12 edges, then executing BFS from a chosen starting vertex, often vertex 0, to propagate through the graph, recording each discovered edge. After traversal, the recorded edges are displayed, representing the MST.

Example: Building the Graph

In main(), the graph would be constructed as follows:

  • Add vertices labeled 'A' through 'I' (0 to 8).
  • Add 12 edges connecting various pairs of vertices to ensure the graph's connectivity and enough complexity to validate the MST process.

Sample Code Snippet



public class BFSMST {


static class Edge {


int start;


int end;


public Edge(int s, int e) {


start = s;


end = e;


}


@Override


public String toString() {


return "(" + start + " - " + end + ")";


}


}


public static void main(String[] args) {


Graph graph = new Graph(9);


// adding vertices 'A' to 'I'


char[] labels = {'A','B','C','D','E','F','G','H','I'};


for(int i=0; i

graph.addVertex(labels[i]);


}


// adding 12 edges to form a connected graph


graph.addEdge(0,1);


graph.addEdge(0,2);


graph.addEdge(1,3);


graph.addEdge(1,4);


graph.addEdge(2,5);


graph.addEdge(2,6);


graph.addEdge(3,7);


graph.addEdge(4,7);


graph.addEdge(5,8);


graph.addEdge(6,8);


graph.addEdge(3,4);


graph.addEdge(5,6);


// MST recording list


List mstEdges = new ArrayList();


// Perform BFS starting from vertex 0


graph.bfsWithEdgeRecording(0, mstEdges);


// Output MST edges


System.out.println("Minimum Spanning Tree edges:");


for(Edge e : mstEdges) {


System.out.println(e);


}


}


}


class Graph {


private final int maxVertices;


private Vertex[] vertexList;


private int[][] adjMat;


private int nVerts;


public Graph(int size) {


maxVertices = size;


vertexList = new Vertex[maxVertices];


adjMat = new int[maxVertices][maxVertices];


nVerts = 0;


for(int i=0; i

for(int j=0; j

adjMat[i][j] = 0;


}


}


}


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 bfsWithEdgeRecording(int startVertex, List mstEdges) {


boolean[] visited = new boolean[nVerts];


Queue queue = new LinkedList();


visited[startVertex] = true;


queue.offer(startVertex);


while(!queue.isEmpty()) {


int v1 = queue.poll();


for(int v2=0; v2

if(adjMat[v1][v2] == 1 && !visited[v2]) {


visited[v2] = true;


queue.offer(v2);


// Record edge in MST


mstEdges.add(new BFSMST.Edge(v1, v2));


}


}


}


}


}

Results and Discussion

Executing the above code with a connected graph of 9 vertices and 12 edges produces a spanning tree that connects all vertices with 8 edges, which is the minimal number for a spanning tree of 9 nodes. Using BFS ensures the shortest path in terms of the number of edges, thus aligning with the properties of a minimum spanning tree in unweighted graphs. This approach demonstrates how traversal algorithms can be adapted for MST construction, emphasizing the importance of capturing parent-child relationships during traversal.

Conclusion

Modifying the BFS algorithm to record edges during traversal effectively produces a minimum spanning tree in an unweighted graph. The method ensures that the resulting set of edges connects all vertices with minimal redundancy, matching the basic properties of an MST. When building complex networks or analyzing connectivity in unweighted graphs, BFS-based MSTs serve as a simple yet powerful tool. Future enhancements may include handling disconnected graphs by generating a minimum spanning forest or integrating real edge weights for algorithms like Kruskal’s or Prim’s.

References

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). The MIT Press.
  • Goodrich, M. T., & Tamassia, R. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.
  • Kleinberg, J., & Tardos, E. (2005). Algorithm Design. Pearson.
  • Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
  • Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press.
  • Tarjan, R. E. (1983). Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics.
  • Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer.
  • Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87–90.
  • Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389–1401.
  • Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50.

Related Assignments