1. | A concept used to answer questions of reachability: can one get from node d to node b in one or more hops? It usually uses an adjacency matrix. |
| |

2. | A graph traversal algorithm that visits sibling nodes before visiting the child nodes. |
| |

3. | A graph traversal algorithm that visits the child nodes before visiting the sibling nodes; it traverses the depth of any particular path before exploring other paths. |
| |

4. | A graph which contains a circuit that visits every edge of the graph once and only once, and ends on the same vertex it began on. |
| |

5. | A graph which contains a circuit that visits every vertex exactly once and ends at the vertex where it started. |
| |

6. | A process in which an approximation to the correct distance is gradually replaced by more accurate values until the optimum solution is reached. |
| |

7. | Algorithm which finds a minimum spanning tree for a connected weighted graph. It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. It started by making each vertex a separate tree in a forest. |
| |

8. | Algorithm which finds a minimum spanning tree for a connected weighted undirected graph. It finds a subset of the edges that forms a tree including every vertex, where the total weight of all edges in the tree is minimized. It adds one vertex at a time to the tree. |
| |

9. | Algorithms for dense graphs use an adjacency _____. |
| |

10. | Algorithms for sparse graphs use an adjacency ____. |
| |

11. | An algorithm that solves the all-pairs shortest path problem for weighted graphs with positive or negative edge weights. |
| |

12. | An algorithm that solves the single-source shortest path problem for weighted graphs with positive or negative edge weights. |
| |

13. | Bellman-Ford is able to detect and report the existence of ________ _____, but it cannot produce a correct answer if they are present. |
| |

14. | Bellman-Ford is different from Dijkstra’s algorithm because it can handle these. |
| |

15. | Breadth-first search is generally implemented using this data structure. |
| |

16. | Depth-first search is generally implemented using this data structure. |
| |

17. | Graph search algorithm which solves the single-source shortest path problem for a graph with non-negative edge path costs. |
| |

18. | Prim’s and Kruskal’s are _____ algorithms. |
| |

19. | Repeatedly removing vertices with in-degree of 0 and their edges from the graph will produce this type of sort. |
| |

20. | The problem of finding a path between two vertices in a graph such that the sum of the weights of its edges is minimized. |
| |

21. | The problem which answers the question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? |
| |

22. | This type of problem involves finding a feasible flow through a single-source, single-sink flow network that is maximum. |
| |