PowerPoint Presentation: Prepared By : Naveen Kumar Gupta Programme : M.Sc.IT Enroll. No. : 120220 Submitted To : Mr. Yash Paul 1
CONTENTS: Brief Introduction About Graph. Path in a Graph. Representation of Graph. Warshall’s Algorithm. Implementation of Warshall’s Algorithm. 2 CONTENTS
PowerPoint Presentation: A Graph is a non-linear data structures. A Graph G is defined as a set of two tuples that is G = (V, E), where V represents set of vertices of G and E represents the set of edges of G. Examples… 3 GRAPH e 2 V5 V1 V5 V2 V3 V4 V6 e 1 e 4 e 3 e 5 e 7 e 6 e 8 e 9 (A) Undirected Graph V1 V2 V4 V3 e 1 e 2 e 3 e 4 e 5 e 6 e 7 (B) Directed Graph V1 V4 V2 V3 (C) Mixed Graph e 1 e 3 e 4 e 2 e 5
PowerPoint Presentation: Fig (A) consists of 6 vertices and 9 edges where V = { V1, V2, V3, V4, V5, V6 } and E = { e1, e2, e3, e4, e5, e6, e7, e8, e9 } and so on where e belongs to set E and e is an ordered pair of two vertices. E.g. e1=(v1, v2) or (v2, v1). When in a graph, two or more than two edges are used to join two vertices such edges are called parallel edges and the graph is called multi-graph. In a graph there may exists two or more directed edges between two vertices and parallel loops are also possible 4 CONTD.. V1 V4 V2 V3 Multi Graph
PowerPoint Presentation: If we consider figure (E) then we have V = {v 1 ,v 2 ,v 3 ,v 4 ,v 5 } E = { (v 1 ,v 2 ), ( v 1 , v 4 ), ( v 2 , v 3 ), (v 3 , v 4 ), (v 4 ,v 5 ), (v 5 ,v 1 ), ( v 5 ,v 2 ), ( v 5 ,v 3 ) } A sequence of edges of a digraph such that the terminal vertex of an edge sequences is the initial vertex of the next edge if exists is called the path. For example, let we have E = { (v 1 ,v 2 ), (v 2 ,v 3 ), (v 3 ,v 4 ), (v 4 ,v 5 ), (v 5 ,v 1 ) } 5 PATH (E) Directed Graph V5 V1 V2 V4 V3 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8
PowerPoint Presentation: If we consider the elements of E, we find that E is a set of 5 tuples, that is e 1 = (v 1 ,v 2 ) e 2 = ( v 2 , v 3 ) e 3 = ( v 3 , v 4 ) e 4 = ( v 4 , v 5 ) e 5 = ( v 5 , v 1 ) Thus we can say that there exists a circular path. 6 CONTD..
PowerPoint Presentation: There is two popular ways that are used to maintain a graph in a computer memory. These are 1. Sequential 2. Linked List Sequential Representation-: The graphs can be represented as matrices in sequential representation. There are two most common matrices these are : a. Adjacency b. Incidence Adjacency matrix-: The adjacency matrix is a sequence matrix with one row and one column for each vertex. If graph G consists of v 1 ,v 2 ,v 3 , …., v n vertices then the adjacency matrix A = [a ij ] of the graph G is the n x n matrix and can be defined as : 7 REPRESENTATION OF GRAPH
CONTD..: 1 if there is an edge between v i and v j A ij = 0 if there is no edge between v i and v j Consider the graph G illustrated in figure (F) which consists of 5 vertices and 7 edges. The set of vertices is as follows : V={v 1 ,v 2 ,v 3 ,v 4 ,v 5 } and the set of edges is : E={(v 1 ,v 2 ), (v 1 , v 3 ), (v 2 , v 1 ), ( v 2 , v 3 ), ( v 2 ,v 5 ), (v 3 ,v 1 ), (v 3 , v 4 ), ( v 4 , v 1 ), ( v 4 , v 5 ), ( v 5 , v 3 )} 8 CONTD.. (F) Directed Graph V5 V1 V2 V4 V3 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 10 e 9
CONTD..: The Adjacency matrix A for G is as follows: v 1 v 2 v 3 v 4 v 5 v 1 0 1 1 0 0 v 2 1 0 1 0 1 A = v 3 1 0 0 1 0 v 4 1 0 0 0 1 v 5 0 0 1 0 0 9 CONTD..
WARSHALL’S ALGORITHM: Warshall’s Algorithm is a shortest path algorithm. With the help of this algorithm we can find the shortest path between two vertices of a graph . If we have a map as shown in figure 1.1 and a pilot wishing to drive from city A to city E will be interested in getting the answer of the following questions: Is there a path from A to E? If there is more path from A to E, which is the shortest one? 10 WARSHALL’S ALGORITHM (1.1) Directed Graph C A B E D
CONTD..: For getting answer of such type of problem there are several algorithm, warshall’s algorithm is one of them . Warshall’s Algorithm-: Let G = (V, E) is a multi-graph with n vertices v 1 ,v 2 ,v 3 ,….,v n . Suppose we want to find a matrix M which gives the length of the shortest path between the vertices of a graph G. Warshall gave an algorithm for this purpose which is efficient to find the shortest path between two vertices in a graph. He had defined n+1, n x n matrices M 0 , M 1 ,….., M n , such as : 1 is there is simple path from v i to v j , which does not use any other vertices except possibly v 1 , v 2 ,…., v k . M k [i][j] = 0 Otherwise 11 CONTD..
CONTD..: For example, suppose A is adjacency matrix of G, replace all those elements of A which are 0 by infinity (or by a very-very large number), which now indicates that there is no edge between the vertices. In this technique we obtain a set of matrices M 0 , M 1 , M 2 , …., M n with the help of following formula : M k [i][j] = Min( M k-1 [i][j], M k-1 [i][j] + M k-1 [k][j] ) Implementation of warshall’s algorithm-: /* SHORTEST PATH */ /* WARSHALL.C */ # include< stdio.h > # define size 10 # define infinity 9999 int a [size][size ]; int m [size ][size ]; 12 CONTD.. Directed Graph A B E D
Implementation of warshall’s algorithm: 13 int i,k,j ; int n; void Input (); void Warshall (); void Output (); /* Input function */ void Input() { printf ("\n Input the number of vertices: "); scanf ("%d", &n); printf ("\n Input adjency matrix\n"); for ( i = 0; i < n; i++) { for ( j = 0; j < n; j++) { scanf ("%d", &a[i][j]); } printf ("\n"); } Implementation of warshall’s algorithm
CONTD…: 14 printf ("\n Adjency matrix \n"); for ( i = 0; i < n; i++) { for ( j = 0; j < n; j++) { printf (" \ t%d ", a[i][j]); } printf ("\n"); } } /* Output function */ void Output() { for ( i = 0; i < n; i++) { for ( j = 0; j < n; j++) { printf (" \ t%d ", p [i][j]); } printf ("\n"); } } CONTD…
CONTD..: 15 /* Shortest path function */ void Warshall () { /* Initialization of matrix m */ for ( i = 0; i < n; i++) { for ( j = 0; j < n; j++) { if (a[i][j] == 0) m [i][j] = infinity; else m[i ][j] = a[i][j]; } } CONTD..
CONTD..: 16 /* Shortest Path evaluation start from here */ for ( k = 0; k < n; k++) { for ( i = 0; i < n; i++) { for ( j = 0; j < n; j++) { if (m[i ][j] <= m[i ][k] + m[k ][j]) m[i ][j]= m[i ][j]; else m[i ][j] = m[i ][k] + m[k ][j]; } } printf ("\n STEP %d \ n",k ); Output(); } } CONTD..
CONTD..: 17 /* Function main */ int main() { Input (); Warshall (); printf ("\n Shortest Path matrix:\n"); Output (); } CONTD..
PowerPoint Presentation: 18 THANK YOU REFRENCES: Expert Data Structures With C By R.B. Patel.