CMPT 360 Study Guide - Final Guide: Linked List, Directed Acyclic Graph, Time Complexity
Document Summary
Given: a directed acyclic graph g = (v, e) Topologically sort g (gives an ordering v1, v2, . , vn of the nodes v , where n = |v |) For i = 1 to n 1: if (vi, vi+1) 6 e: output no"". A path touching all vertices is sometimes called a hamilton path. Any topological ordering must respect all the edges on this path, and must therefore put the vertices in exactly the same order as they appear on the path. The algorithm above will nd this unique topological sort, and con rm the existence of the corresponding hamilton path. On the other hand, if g does not have a hamilton path, the algorithm will nd some topological ordering v1, . , vn, but one of the edges (vi, vi+1) will not be in e. The running time is the same as that of topological sort: o(|v | + |e|).
