Given an undirected unweighted connected graph consisting of n vertices and m edges. The task is to find any spanning tree of this graph such that the maximum degree over all vertices is maximum possible. The order in which you print the output edges does not matter and an edge can be printed in reverse also i.e. (u, v) can also be printed as (v, u).
Examples:
**Input:** 1 / \ 2 5 \ / 3 | 4 **Output:** 3 2 3 5 3 4 1 2 The maximum degree over all vertices is of vertex 3 which is 3 and is maximum possible. **Input:** 1 / 2 / \ 5 3 | 4 **Output:** 2 1 2 5 2 3 3 4
Approach: The given problem can be solved using Kruskal’s algorithm to find the Minimum Spanning tree.
We find the vertex which has a maximum degree in the graph. At first, we will perform the union of all the edges which are incident to this vertex and than carry out normal Kruskal’s algorithm. This gives us an optimal spanning tree.
// Java implementation of the approach
import java.util.*;
public class GFG {
// par and rank will store the parent
// and rank of particular node
// in the Union Find Algorithm
static int par[], rank[];
// Find function of Union Find Algorithm
static int find(int x)
{
if (par[x] != x)
par[x] = find(par[x]);
return par[x];
}
// Union function of Union Find Algorithm
static void union(int u, int v)
{
int x = find(u);
int y = find(v);
if (x == y)
return;
if (rank[x] > rank[y])
par[y] = x;
else if (rank[x] < rank[y])
par[x] = y;
else {
par[x] = y;
rank[y]++;
}
}
// Function to find the required spanning tree
static void findSpanningTree(int deg[], int n,
int m, ArrayList<Integer> g[])
{
par = new int[n + 1];
rank = new int[n + 1];
// Initialising parent of a node
// by itself
for (int i = 1; i <= n; i++)
par[i] = i;
// Variable to store the node
// with maximum degree
int max = 1;
// Finding the node with maximum degree
for (int i = 2; i <= n; i++)
if (deg[i] > deg[max])
max = i;
// Union of all edges incident
// on vertex with maximum degree
for (int v : g[max]) {
System.out.println(max + " " + v);
union(max, v);
}
// Carrying out normal Kruskal Algorithm
for (int u = 1; u <= n; u++) {
for (int v : g[u]) {
int x = find(u);
int y = find(v);
if (x == y)
continue;
union(x, y);
System.out.println(u + " " + v);
}
}
}
// Driver code
public static void main(String args[])
{
// Number of nodes
int n = 5;
// Numbr of edges
int m = 5;
// ArrayList to store the graph
ArrayList<Integer> g[] = new ArrayList[n + 1];
for (int i = 1; i <= n; i++)
g[i] = new ArrayList<>();
// Array to store the degree
// of each node in the graph
int deg[] = new int[n + 1];
// Add edges and update degrees
g[1].add(2);
g[2].add(1);
deg[1]++;
deg[2]++;
g[1].add(5);
g[5].add(1);
deg[1]++;
deg[5]++;
g[2].add(3);
g[3].add(2);
deg[2]++;
deg[3]++;
g[5].add(3);
g[3].add(5);
deg[3]++;
deg[5]++;
g[3].add(4);
g[4].add(3);
deg[3]++;
deg[4]++;
findSpanningTree(deg, n, m, g);
}
}