Introduction of Graph

Graph is a collection of nodes called vertices, and connection between them called edges.

Graph is most popular data structure and consist of vertices or nodes and edges.

A finite set of ordered pair nodes form (u, v) called edge. There are two types of graph, Undirected graph and directed graph.

• When edges in graph have a direction, the graph is called directed graph or digraph and edges are called directed edges.
• When edges in graph do not have a direction, the graph is called undirected graph.

The pair of form (u,v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost. The ordered pair edge (u,v) is not same as (v,u) in case of directed or digraph, But in case of undirected graph both are same.

Example of Directed graph:

The following graph shown below with 4 vertices and 5 edges.

Example of Undirected graph:

The following graph shown below with 5 vertices and 7 edges.

Applications of Graph:

Graphs are used to represent many real life example, some of them are:

• Graphs are used to represent network. Network may include to paths in city, telephone network and circuit network etc.
• Graphs are used in social networks like linkedIn,facebook.For example, In facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender and locale. When users connect they create an edge
• Finding shortest route using GPS/Google Maps/Yahoo Maps etc.
• Search webpage on google, where each page on internet are linked to each other by hyperlinks, each page is vertex and link between two pages called is an edge.
• Network Traffic flow/Shortest path/Minimum spanning tree

Graph representations

Following are the ways of representing a graph:

1. The intuitive representation
2. Adjacency List
3. Adjacency Matrix
4. Incidence Matrix
5. Incidence List

Adjacency Matrix and Adjacency List are most commonly used representation of graph.

Adjacency Matrix

Adjacency matrix is a 2D array of size V x V, where V is number of vertices in graph. Lets an adjancency matrix adj[V][V], a cell adj[i][j]=1 indicates that there is an edge from vertex i to vertex j. adj[i][j] is also can be used to represent cost, weight and distance between vertex i and vertex j.

Adjacency matrix of an undirected graph is always symmetric.

Adjacency matrix of above directed graph.

Adjacency matrix of above undirected graph.

Pros: Easy to implement and follow. Removing and searching an edge from vertex u to vertex v can be done in O(1).

Cons: Consume O(V x V) space even if the graph is sparse. Adding a vertex in graph take O(V^2) time.

Adjacency List

An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists.

Adjacency list representation of the above directed graph.

Adjacency list representation of the above undirected graph.

Pros: space complexity O(|V|+|E|) . In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.

Cons: Finding an edge from vertex u to vertex v is not efficient and can be done in O(V).