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