Graph: edges and vertices. Directed vs. undirected edges. Weighted vs. unweighted edges.
Graph representations:
Adj. list: store an array of lists, one list for each vertex. The list stores pointers to the vertices that are adjacent (connected by outbound edges) to that one.
Adj. matrix: store an n by n
boolmatrix (where n is the number of vertices). To determine whether there is an edge from x to y look inmatrix[x][y].
Breadth-first search: finds shortest paths (in terms of path length) from a source node to as many other nodes are reachable from it, by adding newly discovered nodes to a queue.
Depth-first search: finds paths (not necessarily shortest) from a source node to all reachable nodes. DFS has various useful properties that can expose the structure of the graph (e.g., whether or not it has cycles) while we are exploring it. Example…