Digraph Applications (cont)
Problems to solve on digraphs:
- is there a directed path from s to t?
(transitive closure)
- what is the shortest path from s to t?
(shortest path, #edges)
- are all vertices mutually reachable?
(strong connectivity)
- how to organise a set of tasks?
(topological sort)
- which web pages are "important"?
(PageRank)
- how to build a web crawler?
(graph traversal)
|