5. Consider the following algorithm to check connectivity of a graph defined by

Question

5. Consider the following algorithm to check connectivity of a graph defined by its adjacency matrix. ALGORITHM Connected(A[0..n -1, 0.n - 1]) //Input. Adjacency matrix 0..n-1, 0..n-1]) of an undirected graph G //Output: 1 (true) if G is connected and 0 (false) if it is not if n 1 return 1 //one-vertex graph is connected by definition else if not Connected(AO..n-2, 0..n-2) ) return 0 else for j 0 to n-2 do if A[n-1, j] return 1 return 0 Does this algorithm work correctly for every undirected graph with n > 0 vertices? If you answer yes, indicate the algorithm's efficiency class in the worst case; if you answer no, explain why.

Explanation / Answer

Yes this algorithm works correctly for every undirected graph with n>0 because it is recursively checking for first n-1 nodes graph that whether it is connected or not.If not then it will return 0 which imply not connected ,But if the first n-1 nodes of the graph is connected then it will check whether the nth node is connected to graph or not by checking the adjacency matrix A[n-1,j] and if A[n-1,j] is 1 then this node is also connected to the (n-1) nodes graph but if A[n-1,j] =0 for all 0<=j<=n-2 then this nth node is not connected to the (n-1) nodes graph.So it will retuen 0 which implies graph is not connected.

The efficiency of algorithm in worst case is of order O(n2) where n is the number of nodes in the original graph.

Proof:

The Connected function is called n times by removing the last node each time recursively.

In each Connected function call, in worst case the for loop may run for (i-1) times where i is the number of nodes

in the graph passed to Connected function in current recursive call.

So, total complexity = 1 + 2+ 3 + 4 + ... + (n-1)

= n*(n-1)/2 = O(n2)

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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