Questions Chapter 13 Flashcards
Graphs consist of _______ connected by _______
vertices connected by edges
The two main search algorithms of a graph are:
depth-first search (dfs) and breadth-first search (bfs)
The depth-first search algorithm can be based on a _______; the breadth-first search algorithm can be based on a _______.
dfs based on a stack; bfs based on a queue
How do you tell, by looking at its adjacency matrix, how many edges there are in an undirected graph?
count number of 1s and divide by 2 (assuming the identity diagonal is all 0s)
In a game simulation, what graph entity corresponds to a choice about what move to make?
node
The weight in a weighted graph is a property of the graph’s _________
edges
True or False: The shortest-path problem (SPP) must be carried out on a directed graph
False
Dijkstra’s algorithm finds the shortest path:
a. from one specified vertex to all other vertices
b. from one specified vertex to another specified vertex
c. from all vertices to all other vertices that can be reached along one edge
d. from all vertices to all other vertices that can be reached along multiple edges
a. from one specified vertex to all other vertices
True or False: The rule in Dijkstra’s algorithm is to always put in the tree the vertex that is closest to the starting vertex
True
In the railroad fares example of a weighted graph, a fringe town is one
a. to which the distance is known, but from which no distances are known
b. which is in the tree
c. to which the distance is known and which is in the tree
d. which is completely unknown
a. to which the distance is known, but from which no distances are known
The all-pairs shortest-path problem involves finding the shortest path
a. from the starting vertex to every other vertex
b. from every vertex to every other vertex
c. from the starting vertex to every vertex that is one edge away
d. from every vertex to every other vertex that is one or more edges away
b. from every vertex to every other vertex
The shortest-path problem for weighted graphs involves finding the ________ number of ______ between two ______.
minimum number of edges between two vertices.