2. [10+10-20 points] (Shortest Cycles) Assume, we want to find a shortest direct

Question

2. [10+10-20 points] (Shortest Cycles) Assume, we want to find a shortest directed cycle C in directed graph G- (V,E). To do this, we employ a BFS (breadth-first search) algo- rithm. The BFS algorithm computes the depth of every vertex in a BFS tree. (a) First we look at structural properties of such a shortest cycle C in the BFS tree. Let C-(vi, v2,..., vk) for some k 2 2. (If (u, v) and (v, u) are edges, then (u, v, u) is considered to be a directed cycle of length 2.) Assume vi (for some i with 1 S i 3 k) is the starting point of a BFS, i.e., vi is at depth her vertices O. At which depth are the ot of C? Why?

Explanation / Answer

Solution (a):

At any time during the execution of BFS suppose that Q contains the vertices {v1, v2, ..., vr} with v1 at the head and vr at the tail. Then d[v1] d[v2] ... d[vr] d[v1] + 1.

Let v be any vertex in V[G]. If v is reachable from s then let (s, v) be the minimum number of edges in E[G] that must be traversed to go from vertex s to vertex v. If v is not reachable from s then let (s, v) = .

Solution (b) :

Define: (s, v) from s to v as the minimum number of edges in any path from vertex s to vertex v.

If there is no path from s to v, then (s, v) = .

We require the following results:

1: For any edge (u, v) E, (s, v) (s, u) + 1

2: Upon termination, for each vertex v V ,the value d[v] computed by BFS satisfies d[v] (s, v)

3: During the execution of BFS on a graph G = (V, E), the queue Q contains the vertices

{v1, v2, ..., vr},where v1 is the head of Q and vr is the tail. Then,d[vr] d[v1] + 1 and

d[vi] d[vi+1] for i = 1, 2, . . . , r 1.

4: Suppose that vertices vi and vj are enqueued during the execution of BFS, and that vi

is enqueued before vj.Then d[vi] d[vj] at the time that vj is enqueued.

Finally, using these results, we will now demonstrate correctness of the BFS algorithm, and

justify our claim of BFS yielding shortest path (in terms of number of edges.)

[s, v] = d[v].

Pseudocode:

1.create a queue Q

2.mark v as visited and put v into Q

3.while Q is non-empty

remove the head u of Q

mark and enqueue all (unvisited) neighbours of u

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.