HomeProgramData structure and algorithm

Spanning Tree in data structure and algorithm

What is a Spanning Tree?

A spanning tree is a subset of Grahp G that has all vertices enclosed by the minimum number of edges. Therefore, a spanning tree will not form a cycle and it cannot be interrupted in the middle.

From the above definition we can conclude that each periodic Graph G will have at least one spanning tree. A broken Graph G will not have any spanning trees.

Below is an example of an example of a Ghp and its spanning trees:

Spanning Tree in data structure and algorithm Picture 1

Above we have 3 spanning trees of a periodic graph. A periodic graph can have up to n n-2 spanning trees, where n is the number of nodes. In the above example, n is 3 so 3 3−2 = 3 spanning trees.

Common properties of the spanning tree (Spanning Tree)

We now understand that a Graph can have more than one spanning tree. The following are some of the properties of the cyclic Graph G tree given:

A periodic Ghp can have more than one spanning tree.

All spanning trees of a Graph G have the same number of edges and vertices.

The spanning tree does not have any cycles.

Removing an edge from a spanning tree will cause the Grahp to be non-periodic.

Adding an edge to the spanning tree creates a cycle.

Mathematical properties of the spanning tree (Spanning Tree)

The spanning tree has n-1 edges, where n is the number of nodes (vertices).

From a periodic Graph, by deleting the maximum of e-n + 1 edges, we can construct a spanning tree.

A recurring grahp can have up to n n-2 spanning trees.

Application of the frame tree (Spanning Tree)

Basically, the spanning tree is used to find the shortest path to connect all nodes in a Graph. Common applications of spanning trees are:

  1. Civil network planning
  2. Computer network routing protocol
  3. Cluster Analysis

We explore the following simple example to understand these applications. Imagine an internet in the city as a large graph and now the plan is to deploy network lines so that the shortest wire length can still connect all the nodes. city. That is an example explanation for the application of the spanning tree.

Minimum Spanning Tree (MST)

In a Weighted Graph, a minimum spanning tree is a spanning tree that has the smallest weight of all these Grahp spanning trees. In real life, the weight here can be distance (distance), congestion, traffic load, or any value that can be represented as edges.

Algorithms for the smallest spanning tree

Because of the page length limitation, I will not present the following two algorithms in this chapter. Please click on the following two links to further explore the two most important spanning tree algorithms:

  1. The smallest spanning algorithm of Kruskal
  2. The smallest arithmetic algorithm of Prim

According to Tutorialspoint

Previous article: AVL tree in data structure and algorithm

Next lesson: Heap data structure

3.8 ★ | 11 Vote
Spanning Tree

You should read it

May be interested

  • Queue data structure (Queue)Queue data structure (Queue)
    queue (queue) is an abstract data structure, is something similar to queues in everyday life (queuing).
  • Structure (Struct) in C #Structure (Struct) in C #
    in c #, a structure is a data type. it helps you create a single variable that keeps relevant data of diverse data types. the keyword struct in c # is used to create a structure.
  • Environment settings in Data structuresEnvironment settings in Data structures
    because c and c ++ languages ​​are the languages ​​that almost every university uses to teach, in this chapter i will guide you to install c and c ++ to run the examples in the configuration series. structure and algorithm.
  • Data structure in C / C ++Data structure in C / C ++
    struct in c / c ++ arrays in c / c ++ allow you to define several types of variables that can hold the values ​​of several members of the same data type. but the structure is another type of data in the c / c ++ programming language, which allows you to combine other types of data.
  • Binary Search algorithm (Binary Search)Binary Search algorithm (Binary Search)
    binany search is a fast search algorithm with runtime complexity of Ο (log n). the algorithm of binary search works based on the principle of division and rule (divide and conquer). in order for this algorithm to work correctly, the data set should be in sorted form.
  • Hash Table data structureHash Table data structure
    the hash table data structure is a data structure that stores data in a federated manner. in hash table, data is stored in array format, in which data values ​​have their own index values. accessing data becomes faster if we know the index of the data to find.
  • Structure (Struct) in C programmingStructure (Struct) in C programming
    arrays in c allow you to define several types of variables that can hold the values ​​of several components of the same type. but the structure is another type of data in the c programming language, which allows you to combine other types of data.
  • Graph data structure (Graph)Graph data structure (Graph)
    a graph (graph) is a form of visual representation of a set of objects in which pairs of objects are connected by links. interconnected objects are represented by points called vertices, and links that connect vertices are called edges.
  • What is the best URL structure for SEO?What is the best URL structure for SEO?
    many visitors will reach your website by clicking on a link, so you might be wondering if what's in the url of a particular page is really important.
  • What is algorithm?What is algorithm?
    algorithms (also known as algorithms - english is algorithms) is a finite set of instructions to be executed in a certain order to get the desired result. in general, the algorithm is independent of programming languages, ie an algorithm can be deployed in many different programming languages.

Data structure and algorithm