A graph consists of two sets, a set of vertices V(G) and a set of edges E(G). A pair of vertices forms an edge. A graph can also be represented as G (V, E).
In this graph, the set of vertices V (G) is {A, B, C, D, E}.
The set of edges E (G) is {(A, B)(A, E)(B, C)(C, D)(E, D)(E, A)}.

The various types of graphs are:
1. Undirected Graphs is a graph where directions are not mentioned.
2. Directed Graphs: A directed graph is one in which the vertices can be visited in a particular direction.
3. Weighted Graphs: A weighted graph has a weight associated with each edge. The weight is usually a number, which can be positiveor negative integer.
Matrix Representation Of Graphs
This is the most popular graph representation techniques. Let there be a graph G with n vertices,where n>= 1. The adjacency matrix for the graph G is a two-dimensional nxn array. Consider the following graph.
The adjacency matrix for the graph is as follows.

Step1: Write a 5 X 5 matrix. (Since there are 5 vertices)

Step2: Mark the entries into the matrix. Put 1 where an edge exists between the two vertices and a 0 if there is no edge.
Adjacency Lists
In adjacency lists, the graphs are represented using n linked lists. Here there is one list for each vertex in thegraph G. The nodes in the list represent the vertices that are adjacent to vertex i.
APPLICATIONS OF GRAPHS
The various areas where graphs are appliedare:
Graphs can be used to find the least congested route between two phones in a telephone system Establish the shortest path between the various switching stations of a satellite network Used in a router to determine the shortest path to a web server
Used to determine the shortest path using the drijstkas algorithm
Used to find the shortest path from one city to another
Used to solve the Traveling Salesman problem

Breadth First Search
This is one of the methods of searching a tree structure. In a breadth first search, the search proceeds by checking each node that is reachable from a parent node, before it expands any of these children. Once the search in the parent node is completed, the search then moves on tothe child nodes. The search is terminated when a solution is found.

If the breadth first search is performed on this tree, the first node to be visited is A. The two adjacent nodes thatare then visited are B and C. The remaining nodes visited are D, E, F and G. Thus, the search visits all the nodesthat are present in the graph.
Depth First Search
In Depth-first search the tree is examined to depth before another path is considered. If the depth limit is reached and no solution found, then it is possible to extend the search to the other branchesof the tree that were initially not considered.

Spanning Trees
A graph with no cycles is called a tree. A spanning tree of a graph is a sub graph that contains all the nodes without any cycles. Various kinds of spanning trees are:

MINIMUM SPANNING TREES
A minimum spanning tree of a weighted graph G is the spanning tree whose edges add up to a minimum weight.There can be more than one minimum spanning tree in a graph.

APPLICATIONS
Minimum spanning trees are used in a variety of applications such as constructing networks, in the travellingsalesman problem and many others. In constructing networks, minimum spanning trees describe the way toconnect a set of sites using a minimum length of wire. In the travelling salesman problem, the minimumspanning tree provides a good heuristic for determining the shortest path which is twice the minimum spanning tree.