Graphs

Vertices and edges. A tree is a graph with no cycles. A general graph can loop, so a search has to remember where it has been.

A graph is a set of vertices and a set of edges between them. An undirected edge can be walked both ways: if you can go from 0 to 1, you can go from 1 to 0. A directed edge would not promise the return trip. This course uses undirected edges.

A tree is a graph with no cycles and one path between the nodes that are connected. A general graph may have cycles, so a search that does not remember where it has been will loop forever. Mark a vertex when you first decide to visit it. Waiting until you have already queued it many times wastes work and can blow up the queue.

The walks you learn next answer different questions on the same picture. Breadth-first search answers "fewest edges" when every edge costs the same. Depth-first search answers "can I get there?" and "what else is in this piece?". The drawing underneath is still vertices, edges, and a record of where you have been.