Graph is a data structure that consists of following two components:
- A finite set of vertices also called as nodes.
- A finite set of ordered pair of the form (u, v) called as an edge.
- The pair is ordered because (u, v) is not same as (v, u) in the case of a directed graph(di-graph).
- The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.
- V -> Number of Vertices.
- E -> Number of Edges.
The graph can be classified on the basis of many things, below are the two most common classifications:
- Undirected Graph: The graph in which all the edges are bidirectional.
- Directed Graph: The graph in which all the edges are unidirectional.
- Weighted Graph: The Graph in which weight is associated with the edges.
- Unweighted Graph: The Graph in which there is no weight associated with the edges.
- Time Complexities in a case of Adjacency Matrix:
- Traversal :(By BFS or DFS) O(V^2)
- Space: O(V^2)
- Time Complexities in the case of Adjacency List:
- Traversal :(By BFS or DFS) O(ElogV)
- Space: O(V+E)
- Google map
- Represent network
- Social Networking sites
Representations of Graph:
- Adjacency Matrix
- It is a 2D array of size V x V where V is the number of vertices in a graph.
- Adjacency List
- Implemented using array of linked list.
- Size of the array is equal to number of vertices
- Used to represent a weighted graph
- Weights of edges can be stored in nodes of linked lists
- Incidence Matrix
- Incidence Lis