Topological sort: Given a list of courses required for the major, and the prerequisite list for each course, find a schedule for taking the courses that obeys the prerequisite list.
Minimum spanning tree: Design the layout of the NSF backbone network for the Internet, minimizing the amount of cable that must be laid.
Finding a cycle: Given a list of processes currently executing on the system, the resources each holds, and the resources each needs, determine whether or not progress is possible.
All-pairs-shortest-path: Find the shortest distance between all pairs of cities in the country, for publication in a traveler's guidebook.
Graph coloring: Assign the fewest numbers of registers needed to store variables and temporary results in a procedure.
Graph matching: Assign teachers to courses, so that every course is taught by a qualified teacher.