I am reviewing the 14 coding interview patterns by Fahim ul Haq; what is the usual ordering, or orderings, of source nodes that are added to the source queue in topological sorting?
Suppose I have this adjacency list (not bidirectional) for my graph that's similar to the example given for topological sorting (the link has a picture for what the graph looks like; here, I label the nodes top to bottom, left to right), and all of the nodes are added in the order of index. For readability, I include in-degree.
| Source Node Index | Destination Node Indices | In-degree |
|---|---|---|
| 0 | 2, 3 | 0 |
| 1 | 3, 6 | 0 |
| 2 | 4, 5, 6 | 1 |
| 3 | 5 | 2 |
| 4 | None | 1 |
| 5 | None | 2 |
| 6 | None | 2 |
Obviously nodes indexed 0 and 1 are source nodes, where if I were to use natural ordering by index, I would add them to my source queue right away.
But what happens if these nodes have values, such as this example below?
| Source Node Index | Node Value |
|---|---|
| 0 | 69 |
| 1 | 3 |
| 2 | 15 |
| 3 | 8 |
| 4 | 26 |
| 5 | 104 |
| 6 | 1 |
What are the different orders I can have in topological sorting, in addition to natural ordering by index, to add my nodes with zero in-degrees to the source queue?