Ch 9: Graphs I

Question 1

what is a graph?

Answer 1

a data structure for representing connections among items, and consists of vertices connected by edges

Question 2

what is a vertex(node)?

Answer 2

represents an item in a graph

Question 3

what is an edge?

Answer 3

represents a connection between two vertices in a graph

Question 4

what does it mean for two vertices to be adjacent?

Answer 4

they are connected by a single edge

Question 5

what is a path?

Answer 5

a sequence of edges leading from a source(starting) vertex to a destination(ending) vertex

Question 6

what is path length?

Answer 6

the number of edges in the path

Question 7

what is distance?

Answer 7

the number of edges on the path between two vertices

Question 8

what does the shortest path algorithm do?

Answer 8

minimizes the sum of edges to the destination, not shortest time

Question 9

what is an adjacency list?

Answer 9

• graph representation

- each vertex has a list of adjacent vertices, each list item represents an edge

Question 10

what is the advantage of an adjacency list?

Answer 10

has a size of O(V+E) (v- vertices, e- edges) because each vertex appears once and each edge appears twice

Question 11

what is the disadvantage of an adjacency list?

Answer 11

determining whether the two vertices are adjacent is O(V) because one vertex’s adjacent list must be traversed looking for the other vertex

Question 12

what is a sparse graph?

Answer 12

when each vertex has far fewer edges than the maximum possible

Question 13

in most applications, when a vertex is only adjacent to a fraction of the other vertices, what does it result in?

Answer 13

a sparse graph

Question 14

what is an adjacency matrix?

Answer 14

• graph representation
• each vertex is assigned to a matrix row and column, and a matrix element is 1 if the corresponding two vertices have an edge or is 0 otherwise

Question 15

in an adjacency matrix that is implemented as a 2-d array, what is the run time of accessing elements?

Answer 15

O(1)

Question 16

in an adjacency matrix that is implemented as a 2-d array, what is the run time of determining whether two vertices are adjacent or not?

Answer 16

O(1)

Question 17

what is the key drawback of an adjacency matrix?

Answer 17

size is O(V^2)

Question 18

what is graph traversal?

Answer 18

an algorithm that commonly visits every vertex in a graph in some order

Question 19

what is breadth-first search (BFS)?

Answer 19

a traversal that visits the starting index then all vertices of distance 1 from the vertex, then distance 2, then so on without revisiting a vertex

Question 20

Is BFS unique? Why?

Answer 20

no because there can be multiple pathways

Question 21

explain the BFS traversal algorithm

Answer 21

• enqueues starting vertex into a queue
• while the queue is not empty, dequeue the vertex
• check that dequeued vertex
• enqueue its adjacent vertices that have yet to be discovered
  repeat

Question 22

what does it mean for a vertex to be discovered?

Answer 22

algorithm visited the vector

Question 23

what is a frontier?

Answer 23

vertices in the queue, being vertices thus far discovered but not yet visited

Question 24

what is depth-first search (DFS)?

Answer 24

a traversal that visits a starting vertex then visits every vertex along each path starting from that vertex to the path’s end before backtracking

Question 25

explain the DFS traversal algorithm

Answer 25

• push starting vertex to stack
• while the stack is not empty, pop the vertex from the top
• if vertex has not been visited visit vertex and push adjacent vertices
  repeat