Deck 13: Graphs

Question 1

A(n) __________ is a data structure that consists of a set of vertices (or nodes) and a set of edges (relations) between the pairs of vertices.

Answer 1

graph

Question 2

A vertex is __________ to another vertex if there is an edge to it from that other vertex.

Answer 2

adjacent

Question 3

Suppose an undirected graph G consists of the following sets:
1) V = {New York, Islip, Philadelphia, Chicago, Seattle}
2) E = {{Islip, New York},{New York, Philadelphia},{Philadelphia, Chicago},
{Chicago, Islip},{Chicago, Seattle},{Chicago, New York},{Seattle, New York}}
Which of the following paths consisting of vertices in V represents a cycle?

A) Philadelphia -> Chicago -> Seattle -> New York
B) New York-> Philadelphia -> Chicago -> Seattle -> New York
C) Philadelphia -> Chicago -> Seattle -> New York -> Islip -> Chicago
D) New York-> Philadelphia -> Chicago -> New York -> Islip

Answer 3

New York-> Philadelphia -> Chicago -> Seattle -> New York

Question 4

A graph that is unconnected has no connected components.

Question 5

Any graph that is connected and contains no cycles can be viewed as a(n) __________ by picking one of its vertices (nodes) as the root.

Question 6

The term __________ refers to visiting all the vertices in a graph.

A) traversal
B) disconnection
C) cycle
D) path

Question 7

We can represent all the vertices of a graph (elements of the set V) by integers from 0 up to, but not including, __________.

A) |V| - 2
B) |V| - 1
C) |V|
D) V

Question 8

Complete the definition of an operator== member function for the Edge class. The function compares the source and dest fields only to determine equivalence between two Edge objects.
bool Edge::operator==(const Edge& other)
{
__________
}

Question 9

A(n) adjacency __________ uses a two-dimensional array to represent a graph.

A) list
B) matrix
C) stack
D) queue

Question 10

A dense graph is one in which |E| is close to but less than __________.

A) |V|
B) |V|²
C) |V|³
D) |V|⁴

Question 11

If a graph is dense, the adjacency matrix representation is best, and if a graph is sparse, the adjacency list representation is best.

Question 12

An adjacency list uses less (more) storage when less than (more than) __________ percent of the adjacency matrix would be filled.

Question 13

The breadth-first search algorithm stores identified vertices in a __________.

A) queue
B) stack
C) binary tree
D) B tree

Question 14

Suppose G is an undirected graph consisting of the following sets:
1) V = {0, 1, 2, 3, 4, 5, 6}
2) E = {{0,1},{0,2}, {1,2},{1,3}, {1,4},{2, 5},{2,6}}
Starting at vertex 0, a possible visit sequence representing a breadth-first search of G is _________.

A) 0 1 3 4 2 5 6
B) 0 2 6 5 1 4 3
C) 0 1 2 3 4 5 6
D) 0 3 4 5 6 1 2

Question 15

The breadth-first search algorithm is O(__________).

Question 16

A(n) __________ search algorithm visits an initial vertex, fully explores a single branch and then backtracks to a new vertex (if one exists).

Question 17

Back edges that connect a vertex with its ancestors are part of a depth-first search tree.

Question 18

Excluding the coloring step, the depth-first search algorithm is O(__________).

A) |E|
B) |E|²
C) |E||V|
D) |V|

Question 19

The collection of trees that may be generated by a depth-first search is called a(n) __________.

Question 20

A(n) __________ sort of the vertices of a DAG (directed acyclic graph) is an ordering of the vertices such that if (u, v) is an edge, then u appears before v.

Question 21

The run-time of Dijkstra's algorithm has an upper bound of O(__________).

A) log |V|
B) |E|
C) |V|
D) |V|²

Question 22

A(n) __________ spanning tree is the spanning tree with the smallest cost.

Question 23

In the algorithm to find the minimum spanning tree, d[v] (the shortest distance to v) contains only the length of the final edge.

Question 24

A naive implementation of Prim's Algorithm that does not utilize priority queues is O(__________).

A) |E|
B) |V|
C) |E| log |V|
D) |V|²

Question 25

For a dense graph, the value of |E| is approximately |V|.