- Breadth-first search: Visit every node in a graph.
- Finding cycles: Does the graph have a cycle?
- Reachability:
What other nodes are reachable from a given node?
- Connected components of undirected graph:
Separate nodes into equivalence classes,
so that there is a path between any two nodes in any class.
- Minimal spanning tree: Find a tree that connects
all the nodes in a weighted graph with minimal cost.
- Topological sorting:
Assign a linear ordering to nodes in a directed acyclic graph.
- Single-source-shortest-path:
Find the shortest path from a given node to all other reachable nodes.
- All-pairs-shortest-path:
Find the shortest path between all pairs of nodes.
- Graph coloring: Assign a color to each node so that no two nodes sharing an edge have the same color.

**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.