Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:ahmadh:ch3 [2018/02/07 04:02] – ahmadh | courses:cs211:winter2018:journals:ahmadh:ch3 [2018/02/07 04:06] (current) – ahmadh | ||
|---|---|---|---|
| Line 235: | Line 235: | ||
| (b) the set S of all active nodes in G that have no incoming edges from other active nodes. | (b) the set S of all active nodes in G that have no incoming edges from other active nodes. | ||
| At the start, all nodes are active, so we can initialize (a) and (b) with a single pass through the nodes and edges. Then, each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through all 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 incoming edges to w to drop to zero, then we add w to the set S. Proceeding in this way, we keep track of nodes that are eligible for deletion at all times, while spending constant work per edge over the course of the whole algorithm. | At the start, all nodes are active, so we can initialize (a) and (b) with a single pass through the nodes and edges. Then, each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through all 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 incoming edges to w to drop to zero, then we add w to the set S. Proceeding in this way, we keep track of nodes that are eligible for deletion at all times, while spending constant work per edge over the course of the whole algorithm. | ||
| + | |||
| + | ==== 3.6.2 Comments ==== | ||
| + | |||
| + | I feel like this section was more challenging to understand compared to the rest of the chapter--probably because it was something entirely new to me. The idea of topological ordering seems intuitive and straightforward, | ||
