Undirected Graphs

Question 1

What is the input format used for all API’s?

Answer 1

• Num vertex
• Num edge
• E pairs of values between 0 and v -1

Question 2

What are the two basic requirements for representation?

Answer 2

• Space to accomodate
• Time-efficient

Question 3

What are the 3 data structures we can use for graphs, and what are their caviates?

Answer 3

• Adjacency matrix V x V Boolean with A{vw} = true if adjacent edge. Space cost V^2
• Array of edges using Edge class. adj() implementation would involve examining all edges - time constraint
• Adjacency list - Vertex-indexed array of lists of the vertices adjacent to each vertex, using bags.

Question 4

What is the worst case time to mark vertices connected to given source?

Answer 4

proportional to sum of degrees

Question 5

How do we search an undirected graph using DFS and what do we use to explore multiple edges?

Answer 5

1. First unmarked vertex in current vertex’s adjacency list. Call recursive and mark vertex.
2. First vertex will be first in newly marked vertex’s adjacency list, so skip.
3. Continue forwards until vertex has all edges marked. Once reached, return to previous until unmarked edge present.
4. Once everything checked, dfs() checks vertices on list then the other remaining lists, however all have been marked.

Use stack

Question 6

What is the difference between BFS and DFS?

Answer 6

Taking next vertex from data structure.
* Least recent for BFS
* Most recent for DFS

Question 7

What is the time complexit in the worst case for BFS?

Answer 7

V + E

Question 8

What is the product of the path finding for BFS?

Answer 8

An array edgeTo[], which is a parent-link representation of a tree rooted at s which defines shortest paths from s to every vertex connected to s

Question 9

How does the path-finding in BFS work and what do we use to explore multiple edges?

Answer 9

1. Put source vertex on queue
2. Take next vertex v from queue and mark it
3. Put onto the queue all unmarked vertices that are adjacent to v
4. Continue 2, 3 until queue empty

We use a queue

Question 10

What is a single source path?

Answer 10

Given graph and source vertex, is there a path from s to a given target vertex v? If yes, find path.

Question 11

What is the purpose of the edgeTo[] array in finding paths?

Answer 11

Integer values that give way to find path back to s for each vertex connected to s.
Remember edge v-w that takes us to each vertex w for the first time, setting edgeTo[w] = v