Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 01:32] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 01:34] (current) – [Designing And Analyzing the Algorithm] mugabej | ||
|---|---|---|---|
| Line 10: | Line 10: | ||
| \\ | \\ | ||
| - | | + | **Algorithm** \\ |
| \\ | \\ | ||
| Line 20: | Line 20: | ||
| \\ | \\ | ||
| - | Analysis:\\ | + | **Analysis**:\\ |
| \\ | \\ | ||
| --> | --> | ||
| Line 31: | Line 31: | ||
| -->For each node //w//, the number of incoming edges that //w// has from active nodes \\ | -->For each node //w//, the number of incoming edges that //w// has from active nodes \\ | ||
| --> And a set S of all active nodes in G that have no incoming edges from other active nodes.\\ | --> And a set S of all active nodes in G that have no incoming edges from other active nodes.\\ | ||
| + | \\ | ||
| At the start, we initialize both of the above things with a single pass through the graph since all of the nodes are active. Thus S consists of all of the nodes in G.\\ | At the start, we initialize both of the above things with a single pass through the graph since all of the nodes are active. Thus S consists of all of the nodes in G.\\ | ||
| --> With each iteration, we select a node //v// from the set S and delete it.\\ | --> With each iteration, we select a node //v// from the set S and delete it.\\ | ||
| -->After deleting //v// from S, we go through all of the nodes //w// to which //v// had an edge, and subtract one from the number of active incoming edges that we are maintaining for //w//.\\ | -->After deleting //v// from S, we go through all of the nodes //w// to which //v// had an edge, and subtract one from the number of active incoming edges that we are maintaining for //w//.\\ | ||
| - | --> If this causes the number of active edges to //w// to drop to zero, then we add //w// to the set //w//. | + | \\ |
| + | --> If this causes the number of active edges to //w// to drop to zero, then we add //w// to the set //w//.\\ | ||
| --> Proceeding in this way, we keep track of nodes eligible for deletion at all times, while spending constant work per edge during the execution of the algorithm.\\ | --> Proceeding in this way, we keep track of nodes eligible for deletion at all times, while spending constant work per edge during the execution of the algorithm.\\ | ||
| Thus we get a O(m+n) time. \\ | Thus we get a O(m+n) time. \\ | ||
