Data structure - Graph

GRAPH Types of Graph Terminology Storage Structure 1

Graph 2 A graph is a collection of nodes (or vertices, singular is vertex) and edges (or arcs)  Each node contains an element  Each edge connects two nodes together (or possibly the same node to itself) and may contain an edge attribute A B G E F D C

Formal definition of graph 3 A graph G is defined as follows: G=(V,E) V(G): a finite, nonempty set of vertices E(G): a set of edges (pairs of vertices)

Types of graph Directed graph (digraph) Undirected graph (graph) 4

Undirected graph 5  An undirected graph is one in which the edges do not have a direction  ‘graph’ denotes undirected graph.  Undirected graph:  ( v1, v2 ) in E is un-ordered.  (v1,v2) and (v2, v1) represent the same edge. G1 = ( 4, 6) V(G1) = { 0, 1, 2 , 3 } E(G1) = { (0,1), (0,2), (0,3 (1,2), (1,3), (2,3) }

 Directed graph is one in which the edges have a direction  Also called as ‘digraph’  Directed graph:  < v1, v2 > in E is ordered.  <V1,v2> and <v2, v1> represent the two different edges. 6 G3 = (3, 3) V(G3) = { 0,1,2 } E(G3) = { <0,1> , <1,0> , <1,2> Directed graph

7 A complete graph is a graph that has the maximum number of edges .  for undirected graph with n vertices, the maximum number of edges is n(n-1)/2  for directed graph with n vertices, the maximum number of edges is n(n-1) Complete graph

8 No.of edges = n(n-1)/2 = 4*3/2 = 12/2 = 6 No.of edges = n(n-1)/2 = 7*6/2 = 42/2 = 21 No.of edges = n(n-1 = 3*2 = 6 Complete graph

Adjacent and Incident 9  If (v0, v1) is an edge in an undirected graph, – v0 and v1 are adjacent – The edge (v0, v1) is incident on vertices v0 and v1  If <v0, v1> is an edge in a directed graph – v0 is adjacent to v1, and v1 is adjacent from v0 – The edge <v0, v1> is incident on vertices v0 and v1

Sub- graph A sub-graph of G is a graph G’ such that  V(G’) is a subset of V(G)  E(G’) is a subset of E(G) 10

Path 11  A path is a list of edges such that each node is the predecessor of the next node in the list  A path from vertex vp to vertex vq in a graph G, is a sequence of vertices, vp, vi1, vi2, ..., vin, vq, such that (vp, vi1), (vi1, vi2), ..., (vin, vq) are edges in an undirected graph  The length of a path is the number of edges on it  A simple path is a path in which all vertices, except possibly the first and the last, are distinct

Cycle 12 A cycle is a path whose first and last nodes are the same - A cyclic graph contains at least one cycle - An acyclic graph does not contain any cycles cyclic graph acyclic graph

Connected component  In an undirected graph G, two vertices, v0 and v1, are connected if there is a path in G from v0 to v1  An undirected graph is connected if, for every pair of distinct vertices vi, vj, there is a path from vi to vj  A connected component of an undirected graph is a maximal connected sub-graph. 13

Strongly connected  A directed graph is strongly connected if there is a directed path from vi to vj and also from vj to vi.  A strongly connected component is a maximal sub- graph that is strongly connected 14

Tree A tree is a graph that is  connected  acyclic. 15

Degree 16  The degree of a vertex is the number of edges incident to that vertex  For directed graph,  the in-degree of a vertex v is the number of edges that have v as the head  the out-degree of a vertex v is the number of edges that have v as the tail  if di is the degree of a vertex i in a graph G with n vertices and e edges, the number of edges is 2/)( 1 0    n ide

Graph Representation 19  Adjacency Matrix  Adjacency Lists

Adjacency matrix 20  Let G=(V,E) be a graph with n vertices.  The adjacency matrix of G is a two-dimensional n by n array, say adj_mat  If the edge (vi, vj) is in E(G), adj_mat[i][j]=1  If there is no edge in E(G), adj_mat[i][j]=0  The adjacency matrix for an undirected graph is symmetric  the adjacency matrix for a digraph need not be symmetric

Adjacency matrix - graph 21 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0             0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

Adjacency matrix - digraph 22 0 1 0 1 0 0 0 1 0           0 1 2 0 1 2

23  From the adjacency matrix, to determine the connection of vertices is easy  The degree of a vertex is  For a digraph,  the row sum is the out_degree  the column sum is the in_degree Merits of Adjacency Matrix adj mat i j j n _ [ ][ ]   0 1 ind vi A j i j n ( ) [ , ]    0 1 outd vi A i j j n ( ) [ , ]    0 1

Demerits of adjacency matrix 24  Storage complexity: O(|V|2)  Difficult to insert and delete nodes.

Adjacency list 25  To overcome the problem arise in the adjacency matrix, linked list can be used  The adjacency list contains two lists 1. node list 2. edge list

Adjacency list - digraph 27 Adjacency list Inverse Adjacency list

Merits of adjacency list 28  degree of a vertex in an undirected graph  number of nodes in adjacency list  out-degree of a vertex in a directed graph  number of nodes in its adjacency list  in-degree of a vertex in a directed graph  traverse the whole data structure  Simple way to find out in-degree of vertex in a directed graph  Represent the graph in inverse adjacency list

Data structure - Graph

In this document