Graphs, BFS and DFS

The problem

A graph is a set of nodes (also called vertices) joined by edges. An edge can be undirected (works both ways, like a road) or directed (one way, like a link between web pages). Cities and roads, friends in a network, cells of a maze and "task A must come before task B" are all graphs.

Questions that come up again and again:

• Can I get from node $a$ to node $b$?
• What is the fewest number of edges on a path from $a$ to $b$?
• How many separate pieces (connected components) does the graph have?
• Is there a cycle (a path that returns to its start)?
• Can the nodes be split into two groups with every edge going between the groups (bipartite)?

Notation: $n$ nodes, $m$ edges.