FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 13: Graphs

Show Answer

Share

---

All types

Filters

Study Flashcards

Question 1

Short Answer

Review LaterAdd Note

Review Later

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

Correct Answer

verified

minimum

Question 2

Multiple Choice

Review LaterAdd Note

Review Later

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

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

E) C) and D)
F) None of the above

Correct Answer

verified

A

Question 3

True/False

Review LaterAdd Note

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

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

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.

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

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) { __________ }

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

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

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

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

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

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 vertex is __________ to another vertex if there is an edge to it from that other vertex.

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

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

A graph that is unconnected has no connected components.

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?

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

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