Costo mínimo del árbol de expansión de gráficos dados

Dado un gráfico no dirigido de V Nodes (V > 2) llamados V ₁ , V ₂ , V ₃ , …, V _n . Dos Nodes Vi y V _j están conectados entre sí si y solo si 0 < _| yo – j | ≤ 2 . A cada borde entre cualquier par de vértices (V _i , V _j ) se le asigna un peso i + j . La tarea es encontrar el costo del árbol de expansión mínimo de tal gráfico con Nodes V. Ejemplos:
 
 

Entrada: V = 4 
 

Salida: 13
Entrada: V = 5 
Salida: 21 
 

Enfoque: Comenzando con un gráfico con Nodes mínimos (es decir, 3 Nodes), el costo del árbol de expansión mínimo será 7. Ahora, para cada Node i comenzando desde el cuarto Node que se puede agregar a este gráfico, el i ^-ésimo Node solo puede ser conectado a (i – 1) ^th y (i – 2) ^th Node y el árbol de expansión mínimo solo incluirá el Node con el peso mínimo, por lo que el borde recién agregado tendrá el peso i + (i – 2) . 
 

Entonces, la adición del cuarto Node aumentará el peso total como 7 + (4 + 2) = 13 
De manera similar, al agregar el quinto Node, peso = 13 + (5 + 3) = 21 
… 
Para el Node n ^, peso = peso + (n + ( norte – 2)) . 
 

Esto se puede generalizar como peso = V ² – V + 1 donde V es el total de Nodes en el gráfico.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the minimum cost
// of the spanning tree for the required graph
int getMinCost(int Vertices)
{
    int cost = 0;
 
    // Calculating cost of MST
    cost = (Vertices * Vertices) - Vertices + 1;
 
    return cost;
}
 
// Driver code
int main()
{
    int V = 5;
    cout << getMinCost(V);
 
    return 0;
}

// Java implementation of the approach
class GfG
{
 
// Function that returns the minimum cost
// of the spanning tree for the required graph
static int getMinCost(int Vertices)
{
    int cost = 0;
 
    // Calculating cost of MST
    cost = (Vertices * Vertices) - Vertices + 1;
 
    return cost;
}
 
// Driver code
public static void main(String[] args)
{
    int V = 5;
    System.out.println(getMinCost(V));
}
}
 
// This code is contributed by
// Prerna Saini.

// C# implementation of the above approach
using System;
 
class GfG
{
 
    // Function that returns the minimum cost
    // of the spanning tree for the required graph
    static int getMinCost(int Vertices)
    {
        int cost = 0;
     
        // Calculating cost of MST
        cost = (Vertices * Vertices) - Vertices + 1;
     
        return cost;
    }
     
    // Driver code
    public static void Main()
    {
        int V = 5;
        Console.WriteLine(getMinCost(V));
    }
}
 
// This code is contributed by Ryuga

# python3 implementation of the approach
  
# Function that returns the minimum cost
# of the spanning tree for the required graph
def getMinCost( Vertices):
    cost = 0
  
    # Calculating cost of MST
    cost = (Vertices * Vertices) - Vertices + 1
  
    return cost
  
# Driver code
if __name__ == "__main__":
 
    V = 5
    print (getMinCost(V))

<?php
// PHP implementation of the approach
// Function that returns the minimum cost
// of the spanning tree for the required graph
function getMinCost($Vertices)
{
    $cost = 0;
 
    // Calculating cost of MST
    $cost = ($Vertices * $Vertices) - $Vertices + 1;
 
    return $cost;
}
 
// Driver code
$V = 5;
echo getMinCost($V);
 
#This Code is contributed by ajit..
?>

<script>
 
// Javascript implementation of the approach
 
// Function that returns the minimum cost
// of the spanning tree for the required graph
function getMinCost(Vertices)
{
    var cost = 0;
 
    // Calculating cost of MST
    cost = (Vertices * Vertices) - Vertices + 1;
 
    return cost;
}
 
// Driver code
var V = 5;
document.write( getMinCost(V));
 
// This code is contributed by rrrtnx.
</script>

21

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)