Dado un gráfico completo ponderado no dirigido de N vértices. Hay exactamente M aristas que tienen peso 1 y el resto de aristas posibles tienen peso 0. La array arr[][] da el conjunto de aristas que tienen peso 1. La tarea es calcular el peso total del árbol de expansión mínimo de este gráfico .
Ejemplos:
Entrada: 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) }
Salida: 2
Explicación:
Este es el árbol generador mínimo del gráfico dado:
Entrada: N = 3, M = 0, arr[][] { }
Salida: 0
Explicación:
Este es el árbol de expansión mínimo del gráfico dado:
Enfoque:
Para que el gráfico dado de N Nodes sea Componentes conectados , necesitamos exactamente N-1 aristas de 1 peso . Los siguientes son los pasos:
- Almacene el gráfico dado en el mapa para todos los bordes de peso 1.
- Use set para almacenar los vértices que no están incluidos en ninguno de los componentes conectados de peso 0 .
- Para cada vértice almacenado actualmente en el conjunto , realice un DFS Traversal y aumente el recuento de Componentes en 1 y elimine todos los vértices visitados durante DFS Traversal del conjunto .
- Durante el recorrido DFS , incluya los vértices de peso 0 en un vector y los vértices de peso 1 en otro conjunto . Ejecute un DFS Traversal para todos los vértices incluidos en el vector .
- Luego, al peso total del árbol de expansión mínimo se le da el recuento de componentes: 1.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
2
Complejidad temporal: O(N*log N + M) donde N es el número de vértices y M es el número de aristas.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA