Introduction to Graphs

posted Nov 15, 2013, 11:43 AM by Anupinder Singh   [ updated Mar 3, 2014, 2:13 AM by Anupinder Singh ]
< Previous-Dynamic Programming Technique                                                                                                                                                                          Next - Breadth First Search & its Applications>

Graph is basically a non-linear data structure. A graph consists of a set of objects where some pairs of objects are connected by links. The interconnected objects are called as vertices(nodes), and the links that connect some pairs of vertices are called edges. The edges connecting vertices can be directed or undirected. Therefore two types of graphs exist:
  • Directed Graph : Hold directed edges between vertices 
  • Undirected Graph : Hold undirected edges between vertices.

So formally we can say that, A graph G = ( V , E ) consists of two things:
  • A set 'V' of elements called vertices(nodes).
  • A set 'E' of edges such that each edge 'e' in 'E' is identified with a unique unordered pair [u,v] of nodes in 'V', denoted as 'e'=[u,v]
Examples

 
Now above figure shows a graph consisting of 5 round object. Therefore if we define it as per above mentioned definition it will be written as:

G= ( V , E )

V = { 1,2,3,4,5} (as there are 5 numbered objects in this graph)

E = {[1,2] , [1,3] ,[2,1] , [2,4] , [3,1] , [3,4] , [3,5] , [4,2] , [4,3] ,[4,5] , [5,3] , [5,4] } 

Now if you notice carefully the figure shows only 6 edges, where as set 'E' consists of 12 edges. This is because this graph is undirected graph, so each vertices connected to other vertices will also allows opposite relation to like [u,v] <-> [v,u].



Now lets consider another example with a few changes in same graph


G= ( V , E )

V = { 1,2,3,4,5} (as there are 5 numbered objects in this graph)

E = {[1,2] , [2,4] , [3,1] , [3,4] , [4,5] , [5,3]  } 

Here set 'E' will now only contain those edges which directs to certain node, this is because it is a directed graph. for eg. there is a directed edge from node 1 to node 2, but reverse is not available there fore only one entry will be allowed in 'E' set. 

Next important point about graphs is how they are stored in computer? this is a little tricky work. There are two standard ways to represent a graph G= (V,E) :
  1. A Collection of Adjacency List : Used when 'E' is much less than '|V|2'.
  2. An Adjacency Matrix : used when 'E'  is close to '|V|2'.

 Adjacency List for Undirected Graph mentioned in first figure of graph

Undirected Adjacency List

 Adjacency List for directed Graph mentioned in second figure of graph

Directed Adjacency List


In above figures adjacency list of undirected and directed graphs are shown. If you are aware about data structures this adjacency list actually make used of Linked list data structure. In this we make an array of pointers and then point each index corresponding to each vertices(node) to a linked list containing all end node numbers of the edge. 

 Adjacency matrix for Undirected Graph mentioned in first figure of graph

Adjacency Matrix Undirected Graph

 Adjacency matrix for directed Graph mentioned in first figure of graph

Adjacency Matrix Directed Graph


In above figures adjacency matrix of undirected and directed graphs are shown. This List is basically an array of 'v' by 'v' size and fill value one on the intersection box of start node and end node. For example if we have and edge [1,2] and [2,1] in undirected graph(Left figure) then if you notice the intersection box of 'row 1' and 'column 2' is assigned value '1'. Similarly the intersection of  'row 2' and 'column 1' is also assigned value '1' and so on. Similar setup is used in directed graph.

Degree of Vertex
 
This is the most important term in graphs and is denoted differently for Directed and Undirected Graph. In case of Undirected graph the degree of vertex is the number of edges inclined to it. In case of Directed graphs the degree of vertex is categorized as: OutDegree(number of out going edges) and InDegree(number of incoming edges)

< Previous-Dynamic Programming Technique                                                                                                                                                                          Next - Breadth First Search & its Applications>