Graph is a non-linear data structure containing finite number of nodes and vertices. Graphs are used to represent real-world problems like telephone network, social networks, network of roads, etc. Graph can aslo be used to represent locations, places connected by roads. The connection between nodes or vertices is called edge. Weights (numerical values) can be assigned to the edges of the graph.

In a directed graph direction is shown in the edge, that is, it is known if can we reach to node 'b' from node 'a' or not and back to node 'a' from node 'b' or not.

In undirected graph, edges don't have direction.

If it is possible to reach to a node 'a' from where traversal is started or 'a' is intermediate node and come back to the same node 'a' after visiting intermediate nodes inbetween then the graph is said to contain a Cycle.

A tree containing all the nodes of the graph with minimum weight and with no loops or cycle is called a Minimum Spanning Tree. Minimum spanning tree can be used in telephone network design, computer network design, electric circuit design and many more. In case of computer network or electric circuit, all the componets of the network or circuit can be connected with minimum wire using the concept of minimum spanning tree.

Kruskal's algorithm, Prim's algorithm can be used to find a minimum spanning tree in a graph.

In a weighted graph (a graph in which weigth is given to the edges) we can find a shorted path (path in minium cost) from one node (vertex) to another node. Dijkstra's Algorithm can be used to find a shortest path in a graph.

Topological sorting shows the vertice/s which come before a given vertex 'v' of the directed acyclic graph (DAG). To perform some tasks it becomes necessary to perform some other tasks before that. For example, for a student to study master's level of education it is necessary to complete bachelor's level of education. The dependencies between the tasks can be represented by a graph without a cycle. Topological sort labels all the vertices with number 1 to V (V is the number of vertices in the graph) such that numbers i is < j if and only if there is a path from v_i and v _j. Topological sorting for a digraph with cycle is impossible.

An undirected graph having a path between any two vertices is called a Connected Graph. A graph can be more or less connected as connectivity has a degree. If a graph contains atleast n-different paths between any two verticess then it called n-connected graph. If a vertex 'w' in a path between vertices 'u' and 'v' is removed and there is no other path to reach from vertex 'u' to vertex 'v' then that vertex 'w' is called articulation point or cut vertex. The removal of the cut vertex or articulation point causes a graph to split into two or more graphs. If removal of a edge causes a graph to split into two subgraphs then the edge is called bridge or cut-edge. from a graph

A directed graph is weakly connected if a undirected graph equivalent to the directed graph is connected. A directed graph is strongly connected if each and every pair of vertices have bi-directional paths. A graph may not be strongly connected but may be formed with strongly connected components (SCC).