Question 1: Finding Cycles (a) Give pseudocode for an algorithm which takes a gr

Question

Question 1: Finding Cycles (a) Give pseudocode for an algorithm which takes a graph G and returns the length of the shortest cycle in G. Briefly in one or two sentences) explain and justify the correctness of your algorithm. Assume that G is represented by an adjacency list structure, and that the notation VERTICES(G) and NEIGHBOURS(v) return the vertex set of G and the list of neighbours of vertex v (respectively). You may also assume that the elements of the vertex set are the integers 0,1,2,...n 1 in a graph on n vertices (b)esribe the structure of a worst-cane n-vertex input for your algorithm

Explanation / Answer

We can find the shortest cycle that contains v by running BFS from v, and stopping at the first time that v is reached again (or if BFS terminated without reaching v).

So Run above for each vertex in graph.

An important property of BFS is that if it runs from vertex v, then every vertex s, when it is first reached, then the path that was found from v to s is minimal. Thus, reaching v from v with BFS finds the shortest path from v to itself, namely the shortest cycle that contains v.

We run below algorithm for each vertex in graph G

for each s in [0, n-1]

BFS(s)

maintain the minimum cycle

BFS(int s)

bool *visited = new bool[n]; //mark all node as unvisited at start

for each index in [0, n-1]

visited[index] <- false

endfor

// Create a queue for BFS

list<int> queue;

// Mark the current node as visited and enqueue it to the queue

visited[s] = true;

queue.push_back(s);

// iterator will be used to get all adjacent vertices of a vertex

list<int>::iterator i;

while queue is not empty

// Dequeue a vertex from queue and print it

s <- queue.front()

print s

queue.pop_front() // pop the element from queue

// Get all adjacent vertices of the dequeued

// vertex s. If a adjacent has not been visited,

// then mark it visited and enqueue it

for each i in [adj[s].begin(), adj[s].end()]

if i vertex in not visited

make i vertex as visited

queue.push_back(*i); // push the i vertex to queue

endif

endfor

endwhile

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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