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.

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.