### Operations on Graphs

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

### Examples of Graph Operations

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.