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

Question

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 A[0.n - 1, 0.n - 1]) of an un //Output: 1 (true) if G is connected and 0 (false) if it is n if n 1 return 1 one-vertex graph is connected by def else if not Connected(0..n-2, 0..n-2]) return 0 else for j 0 to n-2 do if Aln-1. Jl return ! 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

Worst case complexity is O(n^2)

Firs n-1 recursive calls..

For each recursive for loop runs n-2 times at max

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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