sort the graphs by precedence or, topologically Key property required for topological sort (TS): the graph must be acyclic There is not a unique ordering following TS: only guarantee is that if w is a descendant of u then w occurs later than u in ordering CS4115 Graph Algorithms Topological Sort Introduction (contd.) ArrangeLoan HireArchitect HireBuilder PlansDevelop ExcavateFoundations BordPleanálaClearance SuperviseWorks BeginWorks HireFurniture MoversOccupancyTake Call the indegree of a node the number of edges entering the node CS4115 Graph Algorithms Topological Sort TopSort Algorithm Repeat n = jVj times: Find a node with indegree= 0 Record this node Remove it and any of its edges void topsort( graph g ) { for( int ct = 1; ct <= vert_ct; ct++ ) { vertex v = find_vertex_of_indegree_zero( ); if (v == null ) fail( "graph has a cycle" ); top_num[ v ] = ct; for each w adjacent to v // edge (v, w) indegree[ w ]--; } } CS4115 Graph Algorithms Topological Sort TopSort Algorithm (contd.) Problem with this code is the O(n2) running time due to O(n) time required to find a zero-indegree vertex, as each vertex will surely become Can improve as follows: For every edge (v; w) we delete, we can check if w’s indegree becomes 0 If yes, store w in special DS (queue or stack) Instead of trawling through all O(n) vertices for one of zero-indegree, just take one from queue / stack Requires an initial search to put all known zero-indegree vertices of graph on some data structure Running time is now O(jVj + jEj) since each edge is processed exactly once and initial checking for indegree of 0 costs O(n) Note check for cycles in graphs CS4115 Graph Algorithms Topological Sort TopSort Algorithm (contd.) void topsort( graph g ) { unsigned int ct = 1; Stack
Website: garryowen.csisdmz.ul.ie | Filesize: -
No of Page(s): 8
Download Data Structures and Algorithms.pdf
No comments:
Post a Comment