Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 01:34] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 01:34] (current) – [Designing And Analyzing the Algorithm] mugabej | ||
|---|---|---|---|
| Line 36: | Line 36: | ||
| -->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. \\ | ||
