Lecture notes on Graphs in Data Structures

what is graph in data structure with example and graphs in data structures and algorithms pdf fee download
DanialOrton Profile Pic
Published Date:09-07-2017
Your Website URL(Optional)
Data structures for graphs There are two reasonable data structures to store graphs: • adjacency matrix • adjacency list An adjacency matrix: letV = v ,v ,...,v . 1 2 n • We store information about the edges of the graph in an n⇥ n arrayA where ⇢ 1 if(v,v )2 E i j Ai,j= (1) 0 otherwise What do we know about the matrix for undirected graphs? the matrix will be symmetric (Ai,j andAj,i will always hold the same value). • If the graph is weighted, Ai,j stores the weight of the edge (v,v ) if that edge exists, and either 0 or 1 if the i j edge doesn’t exist–depends on the application. • Complexity of the adjacency matrix data structure? 2 – Storage requires ⇥( n ) space – Edge Queries are ⇥(1) . 51An adjacency list: Use a1-dimensional arrayA of sizen. • At entryAi, we store a linked-list of neighbours ofv i • If the graph is directed, we store only the out-neighbours. • Each edge (v,v ) of the graph is represented by exactly i j one linked-list node in the directed case, and • by exactly two linked-list nodes in the undirected case • Complexity? – Storage required is ⇥( n+m) – Edgequeriescanbemadein⇥(log( maximum degree))). How? the lists are stored as balanced trees. We now look at two common ways to traverse a graph. 52Breadth-First Search (BFS) Intuition: BFS(vertexv) To start, all vertices are unmarked. • Start atv. Visitv and mark as visited. • Visit every unmarked neighbour u of v and mark each u i i as visited. • Markv finished. • Recurse on each vertex marked as visited in the order they were visited. u1 v v 2 1 1 u2 4 3 u3 BFS of an undirected Graph v v 2 1 2 7 1 4 5 3 5 4 3 8 6 6 53Q:WhatinformationaboutthegraphcanaBFSbeusedtofind? • the shortest path fromv to any other vertexu and this distanced(v). • Whether the graph is connected. Number of connected components. Q: What does the BFS construct? a BFS tree that visits every node connected tov, we call this a spanning-tree. Q:WhatisanappropriateADTtoimplementaBFSgivenanad- jacencylistrepresentationofagraph? a FIFO (first in, first out) queue. which has the operations: • ENQUEUE(Q,v) • DEQUEUE(Q) • ISEMPTY(Q) Q: What information will we need to store along the way? • the current node • the predecessor • the distance so far from v 54The BFS Algorithm We will use pv to represent the predecessor of v, dv to represent the number of edges from v (i.e., the distance from v) andov to represent the order ofv in the search. def BFS(G=(V,E),v): Start BFS on G at vertex v for u in V: Initialize arrays coloru = black ou = -1 not in the BFS yet du = infinity we use infinity to denote pu = NIL "not connected" new queue Q i=1 colorv = green ov = i; dv = 0; pv = NIL ENQUEUE(Q,v) while not ISEMPTY(Q): u = DEQUEUE(Q) for each edge (u,w) in E: if (colorw == black): colorw = green i += 1 ow = i dw = du + 1 pw = u ENQUEUE(Q,w) coloru := red; 55Complexity of BFS(G,v) Q: How many times is each nodeENQUEUEed? at most once, when it is black, at which point it is coloured green. Therefore, the adjacency list of each node is examined at most once, so that the total running time ofBFS is O(n+m) or linear in the size of the adjacency list. NOTES: • BFS will visit only those vertices that are reachable fromv. • Ifthegraphisconnected(intheundirectedcase)orstrongly- connected (in the directed case), then this will be all the vertices. • Ifnot,thenwemayhavetocallBFSonmorethanonestart vertex in order to see the whole graph. Q: Prove that du really does represent the length of the short- est path (in terms of number of edges) fromv tou. 56Depth-First Search Intuition: DFS(G,v) All vertices and edges start out unmarked. • Walk as far as possible away from v visiting vertices • If the current vertex has not been visited, – MarkasvisitedandtheedgethatistraversedasaDFS edge. • Otherwise, if the vertex has been visited, – markthetraversededgeasaback-edge,backuptothe previous vertex • When the current vertex has only visited neighbours left mark as finished (white). • Backtrack to the first vertex that is not finished. • Continue. 57Example. v v Back−edge DFS−edge v v v v Just like BFS, DFS constructs a spanning-tree and gives con- nected component information. Q: Does it find the shortest path between v and all other ver- tices? no 58Implementing a DFS Q: Which ADT would be the most helpful for implementing DFS given an adjacency list representation ofG? A stackS to store edges with the operations • PUSH(S, (u,v)) • POP(S) • ISEMPTY(S) Q:Whatadditionaldata(foreachvertex)shouldwekeepinorder to easily determine whether an edge is a back-edge or a DFS- edge? • dv will indicate the discovery time • fv will indicate the finish time. 59Algorithm DFS(G,s) DFS(G=(V,E),s) for v in V: colorv = black dv = infinity fv =i nfinity pv = NIL new stack S colors = green; ds = 0; ps = NIL time = 0 PUSH(S,(s,NIL)) for edge (s,v) in E: PUSH(S,(s,v)) while not ISEMPTY(S): (u,v) = POP(S); if (v == NIL): // Done with u time += 1 fu = time coloru = white else if (colorv == black): colorv = green time += 1 dv = time pv = u PUSH(S,(v,NIL)) // Marks the end of v’s neighbors for edge (v,w) in E: PUSH(S,(v,w)); 60Complexity of DFS(G,s) Q: How many times does DFS visit the neighbours of a node? • once...when the node is green and the neighbour is black • Therefore, the adjacency list of each vertex is visited at most once. • SothetotalrunningtimeisjustlikeforBFS,⇥( n+m)i.e., linear in the size of the adjacency list. Note that the gold edges, or the DFS edges form a tree called the DFS-tree. Q: Is the DFS tree unique for a given graphG starting ats? no Forcertainapplications,weneedtodistinguishbetweendifferent types of edges inE. 61We can specify edges on DFS-tree according to how they are traversed during the search. • Tree-Edges are the edges in the DFS tree. • Back-Edges are edges from a vertexu to an ancestor ofu in the DFS tree. ⇤ • Forward-Edges are edges from a vertex u to a descen- dent ofu in the DFS tree. ⇤ • Cross-Edges are all the other edges that are not part of the DFS tree (from a vertex u to another vertex v that is neitheranancestornoradescendentofuintheDFStree). ⇤ Only apply to directed graphs. Q:Whichvariablefacilitatesdistinguishingbetweentheseedges? pv Q:HowcanaDFSbeusedtodeterminewhetheragraphGhas any cycles? (Note: A cycle is a path from a vertexu to itself.) It is not hard to see that there is a cycle inG if and only if there are any back-edges when DFS is run. Q: How can we detect back-edges during a DFS? Add a test after the line marked by () in DFS. If the color ofv is green instead of black, then we know that we have seenv before on the current path from the sources. This means that the edge(u,v) is a back edge and therefore forms a cycle. 62Recursive DFS We can rewrite the DFS algorithm recursively which “hides” the stack notion in the recursion. dfs(vertex v, int time) visit(v); v.start = time time++ for each neighbor w of v if w is unvisited dfs(w, time); add edge vw to tree T v.finish = time time++ Weusethetimevariabletonumberthestartandfinishtimesof the nodes which allows us to easily preform a topological sort. 63