Given the number of vertices in a Cycle graph. The task is to find the Total number of Spanning trees possible.
Note: A cycle/circular graph is a graph that contains only one cycle. A spanning tree is the shortest/minimum path in a graph that covers all the vertices of a graph.
Examples:
Input: Vertices = 3 Output: Total Spanning tree = 3 Input: Vertices = 4 Output: Total Spanning tree = 4
Example 1:
For Cycle Graph with vertices = 3
Spanning Tree possible is 3
Example 2:
For Cycle Graph with vertices = 4
Spanning Tree possible is 4
So, the number of spanning trees will always be equal to the number of vertices in a cycle graph.
Implementation:
C++
// C++ program to find number of// spanning trees#include <bits/stdc++.h>using namespace std;// function that calculates the// total Spanning treeint Spanning(int vertices){ int result = 0; result = vertices; return result;}// Driver codeint main(){ int vertices = 4; cout << "Spanning tree = " << Spanning(vertices); return 0;} |
Java
// Java program to find number of // spanning trees import java.io.*;class GFG {// function that calculates the // total Spanning tree static int Spanning(int vertices) { int result = 0; result = vertices; return result; } // Driver code public static void main (String[] args) { int vertices = 4; System.out.println("Spanning tree = " + Spanning(vertices)); }}// This code is contributed // by chandan_jnu.. |
Python3
# Python program to find number of # spanning trees # function that calculates the # total Spanning tree def Spanning( vertices): result = 0 result = vertices return result # Driver code vertices = 4print("Spanning tree = ", Spanning(vertices))# This code is contributed# by Sanjit_Prasad |
C#
// C# program to find number // of spanning treesusing System;// function that calculates // the total Spanning treeclass GFG{public int Spanning(int vertices){ int result = 0; result = vertices; return result;}// Driver codepublic static void Main(){ GFG g = new GFG(); int vertices = 4; Console.WriteLine("Spanning tree = {0}", g.Spanning(vertices));}}// This code is contributed// by Soumik |
PHP
<?php// PHP program to find number of// spanning trees// function that calculates the// total Spanning treefunction Spanning($vertices){ $result = 0; $result = $vertices; return $result;}// Driver code$vertices = 4;echo "Spanning tree = " . Spanning($vertices); // This code is contributed // by Ankita Saini?> |
Javascript
<script>// Javascript program to find number of// spanning trees// Function that calculates the// total Spanning treefunction Spanning(vertices){ result = 0; result = vertices; return result;}// Driver codevar vertices = 4;document.write("Spanning tree = " + Spanning(vertices));// This code is contributed by noob2000</script> |
Output
Spanning tree = 4
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
