Directed Graphs

Question 1

What is a directed cycle and a simple cycle?

Answer 1

• Directed: Path with at least one edge whose first and last vertices are the same
• Simple: Cycle with no repeated edges / vertices

Question 2

What is the adjacency list representation of the DG?

Answer 2

Edge v - w represented as list node containing w in Linked List corresponding to v.Same as undirected graphs however each edge only appears once.

Question 3

What is the difference between the adjacency list representation in DG compared to UDG?

Answer 3

UDG if v is on w’s list, then w is on v’s list. Digraph has no such symmetry.

Question 4

What does the reverse() method do?

Answer 4

Returns copy of digraph with all edges reversed.
Allows clients to find edges that point to each vertex while adj() gives vertices connected by edges pointing from each vertex

Question 5

What are the algorithms for Finding paths and BFS for digraphs?

Answer 5

algorithms are fundamental digraph algorithms. Therefore identical.

Question 6

What is the single and multiple source reachagbility problem?

Answer 6

Given digraph and source s, is there a directed path from s to v?
Is there directed path from any vertex in the set to a given target vertex v?

Question 7

How are the source reachability problems accounted for?

Answer 7

1. Change of DFS
2. 2nd constructor for DFS that takes list of vertices

Question 8

What is the time for DFS in a digraph to mark all reachable vertices from a given set of sources?

Answer 8

Sum of out degrees that are marked.

Question 9

What is topological sort?

Answer 9

Given a graph, put vertices in order such that all its directed from early to late

Question 10

How can a DAG be identified?

Answer 10

The absense of a directed cycle. Can not sort topologically if cycle is present.

Question 11

How do we identiy a directed cycle?

Answer 11

Using DFS.
Stack maintained represents current directed path under consideration.

Question 12

How is the API for DIrectedCycle implemented?

Answer 12

• Creates integer stack Cycle which contain vertices within cycle
• ## Adds boolean array onStack[] where integers represent vertices, Boolean values represent their existnce on cycle and for which the recursive call has not completed. onStack for source will be returned to false once all vertices adjacent to it have been searched.

Question 13

What is the precedence contstrained scheduling problem?

Answer 13

A problem where there are a set of jobs to be completed, constrained to the requisite that certain jobs must be completed before another is completed.

Question 14

How do we create an algorithm for topological sort?

Answer 14

Save argument vertex to recusrive dfs() in a Data structure.
Iterate through structure. We then see all vertices in order determined by nature of structure and whether we do saves before or after recursive calls.

Question 15

What are the 3 vertex orderings?

Answer 15

• Pre-order: Put vertex on Queue before calls
• Post-order: After calls
• Reverse post-order: On Stack after calls

Question 16

Which vertex ordering is topological sort and why?

Answer 16

Considering edge v-w, one of the following three cases must hold when dfs(v) is called:
* dfs(w) has been called and returned (marked)
* dfs(w) not yet called, so v-w will cause dfs(w) to be called and return, before dfs(v) returns.
* dfs(w) has been called and not yet returned when dfs(v) called. This is impossible in DAG, because recursive chain implies path from w to v and v to w complete directed cycle.

In the first two cases, dfs(w) is done before dfs(v), so w after v in reverse post-order.Thus each edge points from a vertex earlier to later.

When visitng a vertex, all descendants reachable from itself have already been visited.

Question 17

What is the time complexity for topological sort?

Answer 17

V + E