Understanding basics of graph is very essential. Many real world problems are effectively represented and solved using graph. Many graph problems can be solved using greedy approach. In this article, we will discuss basics of graph and various graph terminologies. We will talk about graph problems in upcoming articles.

## Basics of Graph

GraphG = (V, E) is defined by a set of vertices (V) and set of edges (E) joining those vertices.

For the graph shown in following figure,

V = {A, B, C, D, E}

E = {AB, AD, AE, BD, BE, DC}

## Weighted Graph

Graph G = (V, E, W) is calledweighted graphif some weight or cost is associated with each of its edges. W represents the set of weight associated with each edge.

A graph representing the distance between cities is a weighted graph, where cost / weight is the distance between two corresponding cities. For the weighted graph is illustrated in following figure,

V = {V1, V2, V3, V4}

E | V_{1}V_{2} | V_{1}V_{3} | V_{1}V_{4} | V_{2}V_{3} | V_{2}V_{4} | V_{3}V_{4} |

W | 10 | 20 | 12 | 15 | 22 | 25 |

## Tree

TreeT = (Vâ€™, Eâ€™) is a subset of Graph G = (V, E), where Vâ€™ is a subset of V and Eâ€™ is a subset of E. Tree does not contain a cycle, while Graph or subgraph can have a cycle.

Following figure shows the graph, its tree and subgraph. Multiple trees and subgraphs are possible for given graph

Tree of Graph G

## Spanning Tree

Spanning tree T = (Vâ€™, Eâ€™) is a tree of connected, undirected, weighted graph G = (V, E, W), which contains all the vertices of G and some or all edges of G. So Vâ€™ = V and Eâ€™ âŠ‚ E.

Following illustrates the spanning tree of graph G.

## Minimum Spanning Tree

Spanning tree T = (Vâ€™, Eâ€™) is a tree of connected, undirected, weighted graph G = (V, E, W), which contains all the vertices of G and some or all edges of G. So Vâ€™ = V and Eâ€™ âŠ‚ E. Graph G can have many spanning trees with a different cost.Minimum spanning treeis a spanning tree with minimum cost.

Graph and its minimum spanning tree are shown in following figure

### Applications of MST

- MST is used in network design
- It is used to implement efficient routing algorithm.
- It is used to solve travelling salesman problem.

Additional Reading: Graph Functions – Click to read