Find weight of MST in a complete graph with edge-weights either 0 or 1
Given an undirected weighted complete graph of N vertices. There are exactly M edges having weight 1 and rest all the possible edges have weight 0. The array arr[][] gives the set of edges having weight 1. The task is to calculate the total weight of the minimum spanning tree of this graph.
Examples:
Input: N = 6, M = 11, arr[][] = {(1 3), (1 4), (1 5), (1 6), (2 3), (2 4), (2 5), (2 6), (3 4), (3 5), (3 6) }
Output: 2
Explanation:
This is the minimum spanning tree of the given graph:
Input: N = 3, M = 0, arr[][] { }
Output: 0
Explanation:
This is the minimum spanning tree of the given graph:
Approach:
For the given graph of N nodes to be Connected Components, we need exactly N-1 edges of 1-weight edges. Following are the steps:
- Store the given graph in the map for all the edges of weight 1.
- Use set to store the vertices which are not included in any of the 0-weight Connected Components.
- For each vertex currently stored in the set, do a DFS Traversal and increase the count of Components by 1 and remove all the visited vertices during DFS Traversal from the set.
- During the DFS Traversal, include the 0-weight vertices in a vector and 1-weight vertices in another set. Run a DFS Traversal for all the vertices included in the vector.
- Then, the total weight of the minimum spanning tree is given the count of components – 1.
Below is the implementation of the above approach:
C++
// C++ Program to find weight of // minimum spanning tree in a // complete graph where edges // have weight either 0 or 1 #include <bits/stdc++.h> using namespace std; // To store the edges of the given // graph map< int , int > g[200005]; set< int > s, ns; // A utility function to perform // DFS Traversal void dfs( int x) { vector< int > v; v.clear(); ns.clear(); // Check those vertices which // are stored in the set for ( int it : s) { // Vertices are included if // the weight of edge is 0 if (!g[x][it]) { v.push_back(it); } else { ns.insert(it); } } s = ns; for ( int i : v) { dfs(i); } } // A utility function to find the // weight of Minimum Spanning Tree void weightOfMST( int N) { // To count the connected // components int cnt = 0; // Inserting the initial vertices // in the set for ( int i = 1; i <= N; ++i) { s.insert(i); } // Traversing vertices stored in // the set and Run DFS Traversal // for each vertices for (; s.size();) { // Incrementing the zero // weight connected components ++cnt; int t = *s.begin(); s.erase(t); // DFS Traversal for every // vertex remove dfs(t); } cout << cnt - 1; } // Driver's Code int main() { int N = 6, M = 11; int edges[][M] = { { 1, 3 }, { 1, 4 }, { 1, 5 }, { 1, 6 }, { 2, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 }, { 3, 4 }, { 3, 5 }, { 3, 6 } }; // Insert edges for ( int i = 0; i < M; ++i) { int u = edges[i][0]; int v = edges[i][1]; g[u][v] = 1; g[v][u] = 1; } // Function call find the weight // of Minimum Spanning Tree weightOfMST(N); return 0; } |
Java
// Java Program to find weight of // minimum spanning tree in a // complete graph where edges // have weight either 0 or 1 import java.util.*; class GFG{ // To store the edges // of the given graph static HashMap<Integer, Integer>[] g = new HashMap[ 200005 ]; static HashSet<Integer> s = new HashSet<>(); static HashSet<Integer> ns = new HashSet<>(); // A utility function to // perform DFS Traversal static void dfs( int x) { Vector<Integer> v = new Vector<>(); v.clear(); ns.clear(); // Check those vertices which // are stored in the set for ( int it : s) { // Vertices are included if // the weight of edge is 0 if (g[x].get(it) != null ) { v.add(it); } else { ns.add(it); } } s = ns; for ( int i : v) { dfs(i); } } // A utility function to find the // weight of Minimum Spanning Tree static void weightOfMST( int N) { // To count the connected // components int cnt = 0 ; // Inserting the initial vertices // in the set for ( int i = 1 ; i <= N; ++i) { s.add(i); } Vector<Integer> qt = new Vector<>(); for ( int t : s) qt.add(t); // Traversing vertices stored in // the set and Run DFS Traversal // for each vertices while (!qt.isEmpty()) { // Incrementing the zero // weight connected components ++cnt; int t = qt.get( 0 ); qt.remove( 0 ); // DFS Traversal for every // vertex remove dfs(t); } System.out.print(cnt - 4 ); } // Driver's Code public static void main(String[] args) { int N = 6 , M = 11 ; int edges[][] = {{ 1 , 3 }, { 1 , 4 }, { 1 , 5 }, { 1 , 6 }, { 2 , 3 }, { 2 , 4 }, { 2 , 5 }, { 2 , 6 }, { 3 , 4 }, { 3 , 5 }, { 3 , 6 }}; for ( int i = 0 ; i < g.length; i++) g[i] = new HashMap<Integer, Integer>(); // Insert edges for ( int i = 0 ; i < M; ++i) { int u = edges[i][ 0 ]; int v = edges[i][ 1 ]; g[u].put(v, 1 ); g[v].put(u, 1 ); } // Function call find the weight // of Minimum Spanning Tree weightOfMST(N); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 Program to find weight of # minimum spanning tree in a # complete graph where edges # have weight either 0 or 1 # To store the edges of the given # graph g = [ dict () for i in range ( 200005 )] s = set () ns = set () # A utility function to perform # DFS Traversal def dfs(x): global s, g, ns v = [] v.clear(); ns.clear(); # Check those vertices which # are stored in the set for it in s: # Vertices are included if # the weight of edge is 0 if (x in g and not g[x][it]): v.append(it); else : ns.add(it); s = ns; for i in v: dfs(i); # A utility function to find the # weight of Minimum Spanning Tree def weightOfMST( N): # To count the connected # components cnt = 0 ; # Inserting the initial vertices # in the set for i in range ( 1 ,N + 1 ): s.add(i); # Traversing vertices stored in # the set and Run DFS Traversal # for each vertices while ( len (s) ! = 0 ): # Incrementing the zero # weight connected components cnt + = 1 t = list (s)[ 0 ] s.discard(t); # DFS Traversal for every # vertex remove dfs(t); print (cnt) # Driver's Code if __name__ = = '__main__' : N = 6 M = 11 ; edges = [ [ 1 , 3 ], [ 1 , 4 ], [ 1 , 5 ], [ 1 , 6 ], [ 2 , 3 ], [ 2 , 4 ], [ 2 , 5 ], [ 2 , 6 ], [ 3 , 4 ], [ 3 , 5 ], [ 3 , 6 ] ]; # Insert edges for i in range (M): u = edges[i][ 0 ]; v = edges[i][ 1 ]; g[u][v] = 1 ; g[v][u] = 1 ; # Function call find the weight # of Minimum Spanning Tree weightOfMST(N); # This code is contributed by pratham76 |
C#
// C# Program to find weight of // minimum spanning tree in a // complete graph where edges // have weight either 0 or 1 using System; using System.Collections; using System.Collections.Generic; class GFG{ // To store the edges // of the given graph static Dictionary< int , int > [] g = new Dictionary< int , int >[200005]; static HashSet< int > s = new HashSet< int >(); static HashSet< int > ns = new HashSet< int >(); // A utility function to // perform DFS Traversal static void dfs( int x) { ArrayList v = new ArrayList(); ns.Clear(); // Check those vertices which // are stored in the set foreach ( int it in s) { // Vertices are included if // the weight of edge is 0 if (g[x].ContainsKey(it)) { v.Add(it); } else { ns.Add(it); } } s = ns; foreach ( int i in v) { dfs(i); } } // A utility function to find the // weight of Minimum Spanning Tree static void weightOfMST( int N) { // To count the connected // components int cnt = 0; // Inserting the initial vertices // in the set for ( int i = 1; i <= N; ++i) { s.Add(i); } ArrayList qt = new ArrayList(); foreach ( int t in s) qt.Add(t); // Traversing vertices stored in // the set and Run DFS Traversal // for each vertices while (qt.Count != 0) { // Incrementing the zero // weight connected components ++cnt; int t = ( int )qt[0]; qt.RemoveAt(0); // DFS Traversal for every // vertex remove dfs(t); } Console.Write(cnt - 4); } // Driver's Code public static void Main( string [] args) { int N = 6, M = 11; int [,]edges = {{1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}}; for ( int i = 0; i < 11; i++) g[i] = new Dictionary< int , int >(); // Insert edges for ( int i = 0; i < M; ++i) { int u = edges[i, 0]; int v = edges[i, 1]; g[u][v] = 1; g[v][u] = 1; } // Function call find the weight // of Minimum Spanning Tree weightOfMST(N); } } // This code is contributed by rutvik_56 |
Javascript
<script> // Javascript program to find weight of // minimum spanning tree in a // complete graph where edges // have weight either 0 or 1 // To store the edges // of the given graph let g = new Array(200005); for (let i = 0; i < 200005; i++) g[i] = new Map(); let s = new Set(); let ns = new Set(); // A utility function to // perform DFS Traversal function dfs(x) { let v = []; // Check those vertices which // are stored in the set for (let it of s.values()) { // Vertices are included if // the weight of edge is 0 if (g[x].get(it) != null ) { v.push(it); } else { ns.add(it); } } s = ns; for (let i of v.values()) { dfs(i); } } // A utility function to find the // weight of Minimum Spanning Tree function weightOfMST(N) { // To count the connected // components let cnt = 0; // Inserting the initial vertices // in the set for (let i = 1; i <= N; ++i) { s.add(i); } let qt = [] for (let t of s.values()) qt.push(t); // Traversing vertices stored in // the set and Run DFS Traversal // for each vertices while (qt.length != 0) { // Incrementing the zero // weight connected components ++cnt; let t = qt[0]; qt.shift(); // DFS Traversal for every // vertex remove dfs(t); } document.write(cnt - 4); } // Driver's Code let N = 6, M = 11; let edges = [ [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 3, 4 ], [ 3, 5 ], [ 3, 6 ] ]; // Insert edges for (let i = 0; i < M; ++i) { let u = edges[i][0]; let v = edges[i][1]; g[u].set(v, 1); g[v].set(u, 1); } // Function call find the weight // of Minimum Spanning Tree weightOfMST(N); // This code is contributed by unknown2108 </script> |
2
Time Complexity :O(N*log N + M) where N is the number of vertices and M is the number of edges.
Auxiliary Space: O(N)
Contact Us