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