Graph data structures for ppt for understanding.pptx

Graph PPt

1. UNIT-5 Graphs: Introduction Applications of graphs Graph representations graph traversals Minimal Spanning Trees.

2. Introduction to Graphs Another non linear data structure. In tree structure, there is a hierarchical relationship between parent and children, that is, one parent and many children. On the other hand, in graph, the relationship is from many parents to many children. Definition-A graph G = ( V ,E) is composed of: V : set of vertices(or nodes) E : set of edges connecting the vertices in V An edge e = (u,v) is a pair of vertices Example: a b c d e V = {a,b,c,d,e} E = {(a,b),(a,c),(a,d),(b,e), (c,d),(c,e),(d,e)}

3. Graph terminology Digraph - A digraph is also called a directed graph . It is a graph G, such that, G=<V,E>, where V is the set of all vertices and E is the set of ordered pair of elements from V. Edges have directions v= A,B,C,D E=((A,B),(A,C),(A,D),(D,B)) C D A B A B C D These are directed graphs G directed if edges ordered pairs (u,v)  u  v G undirected- i f e dg e s u  nord e r e d p a i r s {u,v}

4. Adjacent vertices If two nodes are connected by an edge, they are neighbors (and the nodes are adjacent to each other). The size of a graph is the number of nodes in it The empty graph has size zero (no nodes). Loop - An edge that connects the vertex with itself Degree of a Vertex- the number of edges connected to that vertex F o r d i r e c t e d g r a p h , the in-degree of a vertex v is the number of edges incident on to the vertex. the out-degree of a vertex v is the number of edges emanating from that vertex. Examples 3 3 3 1 2 3 3 2 1 2 3 3 3 4 5 6 1 1 1 1 directed graph in-degree out-degree 1 2 in:1, out: 1 in: 1, out: 2 in: 1, out:

5. p a t h : sequence of vertices v 1 ,v 2 ,. . .v k such that consecutive vertices v i and v i+1 are adjacent . a d e c b a b c d e a b e d c no vertex is repeated simple path : a b c d e b e c Cycle - some path with distinct vertices except that the last vertex is the same as the first vertex a c d a a b c d e Para ll el e d g e s - i f t h ere are on e o r M o re t h an on e e d g es b e t w een t h e s a m e p a i r o f v er t i ce s .

6. connected A g ra p h w i t hou t c y c l es i s ca l l ed a c y c li c g r a ph. Sub graph is a graph with subset of vertices and edges of a graph. A graph is called a simple graph if it has no loops and no parallel edges. A graph is termed as weighted graph if all the edges in it are labeled with some weights. A c o m p l ete g r a ph i s a g ra p h i f e v ery nod e i n a g ra p h i s c o n n e c t ed to every other node. Two vertices are said to be connected if there is a path from v i to v j or v j to v i connected graph : any two vertices are connected by some path. if there is a path from v i to v j and v j to v i . A directed graph is said to be strongly connected if for every pair of distinct vertices v i ,v j in G, there is a path from v i to v j and also from v j to v i . Weakly connected graph- if a graph is not strongly

7. D B C Acyclic graph A A B D S t r on g l y C onn ec t ed A B C D E C o m p l e t e G ra p h Weighted Graph D B C Cyclic graph A

8. 1 2 3 1 2 1 2 3 ( i v ) ( i ) ii) (iii) (a) S o m e o f t h e s u b g ra p h o f G 1 1 2 3 G 1 1 1 2 ( iii ) ( i ) ( ii ) ( b ) S o m e o f t h e s u b g ra p h o f G 2 1 2 G 2

9. More definitions : Loop C D An edge that connects the vertex with itself Or an edge whose starting and end vertices are same A B

10. Even More Terminology connected not connected connected graph : any two vertices are connected by some path At least two vertices are not connected in a graph is called disconnected graph.

11. 1 2 3 1 2 1 2 3 (iv) ( i ) (ii) (iii) (a) S o m e o f t h e s ub g ra p h o f G 1 1 1 1 2 ( i v ) 2 (iii) ( b ) S o m e o f t h e s ub g ra p h o f G 3 ( i ) ( i i ) 1 2 3 G 1 1 2 G 3 Subgraphs Examples

12. Simple graph Simple graph- A graph (digraph) if it does not have any loops or parallel edges (edge from v1 to v2 and v2 to v1) is called simple graph.

13. Representation of a Graph T h ere are t w o w a y s o f re p re s e n t i n g a g ra p h i n m e m o r y : Sequential Representation by means of Adjacency Matrix. Linked Representation by means of Linked List.

14. Adjacency Matrix A B C D E A B C D E 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 Adjacency Matrix is a bit matrix which contains entries of only and 1 Since it stores the information of whether the adjacency vertices are present or not. The connected edge between two vertices is represented by 1 and absence of edge is represented by 0. This representation uses a square matrix of order n x n, where n is the number of vertices in the graph. Adjacency matrix of an undirected graph is symmetric. A B C D E

15. Linked List Representation A B C D N E B C D NULL A B E NULL D A C D NULL A B E NULL C C D NULL A B C D E I t s a v es t h e m e m o r y . The number of lists depends on the number of vertices in the graph. The header node in each list maintains a list of all adjacent vertices of a node .

16. U nd i rec t ed G ra p h A d j ace n cy L i s t A d j ace n cy Ma t r i x

17. D i rec t ed G ra p h A d j ace n cy L i s t A d j ace n cy Ma t r i x

18. Comparison among various representations Adjacency matrix representation always requires n x n matrix with n vertices, regardless of the number of edges. But from the manipulation point of view, this representation is the best. Insertion, deletion and searching are concerned, in some cases, linked list representation has an advantage, but overall performance is consider, matrix representation of graph is more powerful than all

19. Graph Traversal Techniques There are two standard graph traversal techniques: D epth - F i r s t Se a rch ( DF S) Bre a dth - F i r s t Se a rch (B F S) Traversing a graph means visiting all the vertices in the graph exactly once. DFS and BFS traversals result an acyclic graph. DFS and BFS traversal on the same graph do not give the same order of visit of vertices. The order of visiting nodes depends on the node we have selected first and hence the order of visiting nodes may not be unique.

20. Depth-First Search DF S i s s i m il a r to the i n o rder tr a v er s a l o f a tree St a ck i s u s ed to i m p l e m ent the D ept h- F i r s t- Se a rch. DF S f o ll o w s the f o ll o w i n g ru l e s : Select an unvisited node X, visit it, and treat as the current node Find an unvisited adjacent of the current node as Y, visit it, a nd m a ke i t the new current n o de; Repeat step 1 and 2 till there is a ‘dead end’. dead end means a vertex which do not have adjacent nodes or no more nodes can be visited. after coming to a dead end we backtracking along to its parent to see if it has another adjacent vertex other than Y and then repeat the steps 1,2,3. until all vertices are visited.

21. Depth-First Search A stack can be used to maintain the track of all paths from any vertex so as to help backtracking. Initially starting vertex will be pushed onto the stack. To visit a vertex, we are to pop a vertex from the stack, and then push all the adjacent vertices onto it. A list is maintained to store the vertices already visited. When a vertex is popped, whether it is already visited or not that can be known by searching the list. If the vertex is already visited, we will simply ignore it and we will pop the stack for the next vertex to be visited. This procedure will continue till the stack not empty

22. Breadth First Traversal: The breadth first traversal is similar to the pre-order traversal of a binary tree. The breadth first traversal of a graph is similar to traversing a binary tree level by level (the nodes at each level are visited from left to right). All the nodes at any level, i, are visited before visiting the nodes at level i + 1. To implement the breadth first search algorithm, we use a queue. BFS follows the following rules: Select an unvisited node x, visit it, have it be the root in a BFS tree being formed. Its level is called the current level. From each node x in the current level, visit all the unvisited neighbors of x. The newly visited nodes from this level form a new level that becomes the next current level. Repeat step 2 until no more nodes can be visited. If there are still unvisited nodes, repeat from Step 1.

23. B E T h e D e p t h F i r s t Search T ree O r d er : A , B, E, D , C D C A B D C E T h e Brea d t h F i r s t Search T ree O r d er : A , B, C , D , E A B E A D C G r a p h

24. A B C D E G H I DF S T ra v er s a l Ord er A B C F E G D H I F A B C D E G H BFS Traversal Order A B D E C G F H I F I

25. Practice problems v1 v2 v6 v 3 v7 v5 v 8 v4 D f s - B f s-

26. Applications of Graphs Electronic circuits Printed circuit board Integrated circuit T r a n s p o r t a t i o n n e t w o r k s Highway network Flight network Computer networks Local area network Internet Web Databases Entity-relationship diagram

27. A spanning tree of a graph is just a sub graph that contains all the vertices and i s a t ree( w i t hou t a n y c y c l es i n a g ra ph ) A g ra p h m ay h a v e m a n y s p a nn i n g t ree s . o r o r o r S o m e Sp a nn i ng T rees fr o m Gr a ph A Gr a ph A Sp a n n i n g T r ee s

28. Minimum spanning tree Take an example that connect four cities in India like vijayawada, hyderabad, banglore and mumbai by a graph Hyderabad M u m b a i B a ng l o re v i j a y awa d a 270 km 980 km 580 km 1000km Find a short distance to cover all four cities 700 km 650

29. M i n i m u m Sp a n n i n g T r ee s 5 2 1 3 4 2 1 3 The minimum spanning tree for a given graph is the spanning tree of minimum cost for that graph. We i g hted Gr a ph M i n i m um Sp a nn i ng T ree 7 A l g o r i t h m s t o f i n d M i n i m u m S p a nn i n g T rees are: K r u sk a l ‘s A l g o r i th m Prim‘s Algorithm

30. K ru s k a l ’ s a l g o ri t hm Kruskal’s algorithm finds the minimum cost spanning tree by selecting the edges one by one as follows. Draw all the vertices of the graph. Select the smallest edge from the graph and add it into the spanning tree (initially it is empty). Select the next smallest edge and add it into the s pann i n g t r ee . Repeat the 2 and 3 steps until that does not form any cycles.

31. C F E A B D 5 6 4 3 2 1 2 3 2 4 M i n i m um Sp a nn i ng T ree f o r the a b ov e g r a ph i s : C F E A B D 3 2 1 2 2

32. Walk-Through 5 A H B E G 3 2 4 Co n s i d e r a n und i r e c t e d , wei gh t g r a p h C 3 6 D 1 4 3 F 4 8 4 3 10

33. Sort the edges by increasing edge weight edge d v (D,E) 1 (D,G) 2 (E,G) 3 (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

34. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2 (E,G) 3 (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

35. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3 (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

36. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3 (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10 Accepting edge (E,G) would create a cycle

37. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3 (C,F) 3 (B,C) 4 5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

38. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3 (B,C) 4 5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

39. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4 5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

40. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4 (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

41. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4  (B,F) 4 (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

42. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4  (B,F) 4  (B,H) 4 (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

43. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4  (B,F) 4  (B,H) 4  (A,H) 5 (D,F) 6 (A,B) 8 (A,F) 10

44. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B E D C G 3 2 4 6 3 4 3 F 4 8 4 3 10 edge d v (B,E) 4  (B,F) 4  (B,H) 4  (A,H) 5  (D,F) 6 (A,B) 8 (A,F) 10

45. Select first |V|–1 edges which do not generate a cycle edge d v (D,E) 1  (D,G) 2  (E,G) 3  (C,D) 3  (G,H) 3  (C,F) 3  (B,C) 4  5 1 A H B F E D C G 2 3 3 3 edge d v (B,E) 4  (B,F) 4  (B,H) 4  (A,H) 5  (D,F) 6 (A,B) 8 (A,F) 10 Done Total Cost =  d v = 21 4 } n o t considere d

46. Prim’s algorithm P r i m ’ s a l g o r it hm f i n d s t h e m i n i m um c o s t selecting the edges one by one as follows. 1. All vertices are marked as not visited s p a n n i ng t r e e by 2. Any v e r t e x v y o u li ke i s c h o s e n a s s t a r t i ng marked as visited (define a cluster C ). v e r t e x a n d is The smallest- weighted edge e = (v,u) , which connects one vertex v inside the cluster C with another vertex u outside of C , is chosen and is added to the MST. The process is repeated until a spanning tree is formed.

47. Walk-Through K d v p v A F   B F   C F   D F   E F   F F   G F   H F   4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 2 Initialize array

48. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 K d v p v A B C D T  E F G H 2 Start with any node, say D

49. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Update distances of adjacent, unselected nodes K d v p v A B C 3 D D T  E 25 D F 18 D G 2 D H 2

50. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Select node with minimum distance K d v p v A B C 3 D D T  E 25 D F 18 D G T 2 D H 2

51. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Update distances of adjacent, unselected nodes K d v p v A B C 3 D D T  E 7 G F 18 D G T 2 D H 3 G 2

52. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Select node with minimum distance K d v p v A B C T 3 D D T  E 7 G F 18 D G T 2 D H 3 G 2

53. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Update distances of adjacent, unselected nodes K d v p v A B 4 C C T 3 D D T  E 7 G F 3 C G T 2 D H 3 G 2

54. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Select node with minimum distance K d v p v A B 4 C C T 3 D D T  E 7 G F T 3 C G T 2 D H 3 G 2

55. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Update distances of adjacent, unselected nodes K d v p v A 10 F B 4 C C T 3 D D T  E 2 F F T 3 C G T 2 D H 3 G 2

56. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Select node with minimum distance K d v p v A 10 F B 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H 3 G 2

57. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Update distances of adjacent, unselected nodes K d v p v A 10 F B 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H 3 G 2 Table entries unchanged

58. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Select node with minimum distance K d v p v A 10 F B 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H T 3 G 2

59. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Update distances of adjacent, unselected nodes K d v p v A 4 H B 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H T 3 G 2

60. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Select node with minimum distance K d v p v A T 4 H B 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H T 3 G 2

61. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Update distances of adjacent, unselected nodes K d v p v A T 4 H B 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H T 3 G 2 Table entries unchanged

62. 4 25 A H B E D C G 7 2 10 18 3 4 3 F 7 8 9 3 10 Select node with minimum distance K d v p v A T 4 H B T 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H T 3 G 2

63. 4 A H B F E D C G 2 3 4 3 3 Cost of Minimum Spanning Tree =  d v = 21 K d v p v A T 4 H B T 4 C C T 3 D D T  E T 2 F F T 3 C G T 2 D H T 3 G 2 D o n e

64. C E D 3 2 1 2 M i n i m um Sp a nn i ng T ree f o r the a b ov e g r a ph i s : A B C F E A B D 5 6 4 3 4 2 1 2 3 2 A B C D E F A - 5 4 6 2 - B 5 - - 2 - 3 C 4 - - - 3 - D 6 2 - - 1 2 E 2 - 3 1 - 4 F - 3 - 2 4 - Adjacency matrix

65. 1 3 4 6 5 2 6 3 6 5 5 1 6 4 2 5 E x e r c i s e :