I have come across an exam review question that I am stuck on. The question states:
Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram:
This is what I was able to come up with: e, c, b, j, m, l, a, i, k, d, u, t, s, r, g, o, h, p, f, n
I am also certain this isn't correct..
Any Explanation is much appreciated!
Note that $h$ is the minimum element in that partial order, so it must precede every other element in any compatible linear order. Delete $h$ and its outgoing edges from the Hasse diagram; what’s left has two minimal elements, $p$ and $o$, and you can put either of them next after $h$ in the linear order. I’ll take $p$ next, so at this point my (partial) linear order is $hp$. Delete $p$ and its outgoing edges; the remaining Hasse diagram has minimal elements $j$, $f$, and $o$, and you can put any of them next after $p$. I’ll use $o$, so my linear order is now $hpo$. After I remove $o$ and its outgoing edges, the Hasse diagram that remains has minimal elements $j$, $f$, $n$, and $g$, and I can put any of them after $o$ in my linear order.
Now just continue the procedure until you’ve exhausted the vertices. There is more than one compatible linear order.