计算给定图的最小生成树代价

给定一个包含 V 个节点 (V > 2) 的无向图，节点命名为 V1, V2, V3, …, Vn。当且仅当 0 <

≤ 2 时，两个节点 Vi 和 Vj 相互连接。任意顶点对 (Vi, Vj) 之间的边的权重被赋值为 i + j。我们的任务是找到具有 V 个节点的此类图的 最小生成树 的代价。

示例:

> 输入: V = 4

>

> !image

>

> 输出: 13

>

>

> 输入: V = 5

> 输出: 21

解决思路:

让我们从包含最少节点（即3个节点）的图开始，此时最小生成树的代价为7。现在，对于从第四个节点开始添加到图中的每个节点 i，第 i 个 节点只能连接到 (i – 1) 个 节点和 (i – 2) 个 节点。为了构成最小生成树，我们只会包含权重最小的那条边，因此新添加的边的权重将为 i + (i – 2)。

> 因此，添加第四个节点将使总权重增加为：7 + (4 + 2) = 13

> 同理，添加第五个节点：权重 = 13 + (5 + 3) = 21

> …

> 对于第 n 个节点，权重 = 上一权重 + (n + (n – 2))。

这可以被归纳为公式：权重 = V² – V + 1，其中 V 是图中的总节点数。

下面是上述方法的实现：

C++

// C++ implementation of the approach
#include 
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

// 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#

// 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

# 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

JavaScript

// 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.

输出:

21

复杂度分析:

• 时间复杂度: O(1)
• 辅助空间: O(1)