#### What is Graph data structure ?

The graph is a set of vertices connected with the help of edges. A graph may be directed or undirected, and all the vertices are connected in the graph. We can represent a graph using an array of vertices and a two-dimensional array for edges. We can perform basic operations on graphs: adding a vertex, displaying vertex, adding edges, etc.

#### Spanning Tree

A spanning tree is a tree that connects all the vertices of the graph and the lower number of edges. Therefore, the spanning tree is always connected. Also, the spanning tree has never had a cycle. A spanning tree is always defined by a graph and remains a subset of that graph. Thus, a disconnected graph can never have a spanning tree.

- Connected graph :A connected graph is a graph where we can access any vertex from any vertex. Therefore, all vertices are connected on a connected graph in at least one way.
- Undirected graph :A graph where the edges have no specific direction. In the unadulterated graph, the edges vary.
- Directed graph : The edges do not match in this case. Therefore, we can move from one end to the other. At each end, there is a corresponding guide.
- Simple graph : A simple graph without cycles and loops.

#### Applications of spanning tree

- It is used to implement routing protocol in networking
- For clustering, i.e., for grouping the same type of object under one category
- For finding paths in map
- In electrical grid method
- While planning civil, water supply, and telecommunication network.

#### Description of a spanning tree:

Each graph is not directed and connected to a minimum of one opening tree. Consider a graph with V vertices and E number of edges. After that, we will represent a graph like G (V, E). Its open tree will be represented as G ’(V, E’), where E ’⊆ E and the number of vertices remain the same. Therefore, the tree that produces G’s is a G-branch with its own set of the same vertex, but the edges may differ.