Consider the following algorithm to check whether a graph defined by its adjacen

Question

Consider the following algorithm to check whether a graph defined by its adjacency matrix is complete. ALGORITHM GraphComplete (A[o..n - 1, 0..n - 1]) //Input: Adjacency matrix A[..n-1, o..n-1) of an undirected graph G /lOutput: 1 (true) if G is complete and o (false) otherwise if n = 1 return 1/one-vertex graph is complete by definition else if not GraphComplete(A[o..n - 2, o..n - 2]) return o else for j 0 to n-2 do ifA[n-1, j] = o return o return1 What is the algorithm's efficiency class in the worst case?

Explanation / Answer

1)ALGORITHM Connected(A[0..n - 1, 0..n - 1])

//Input: Adjacency matrix A[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

2)if n = 1 return 1 //one-vertex graph is connected by definition

3)else

4)if not Connected (A[0..n-2,0..n-2]) return 0

5)else for j <--- 0 to n - 2 do

6)if A[n - 1, j] return 1

7)return 0

The given algorithm does not work for every undirected graph with n>0 vertices.
But the given algorithm works for some undirected graphs, in which each node must have at least one out edge to any one of its lower numbered vertices, because the code in lines 5 and 6(for and if) returns 1 only if the vertex n-1 have out edge to vertices 0 to n-2(lower than n-1)(i.e only when A[n-1,j] =1)
That is, if the vertices is numbered as n, then the vertex n must have an out edge from n to any one of vertices that are numbered lower than n(i.e vertex n-1,vertex n-2,…vertex 0).
The given algorithm works for the following graphs, because each vertex have out edge to its anyone of lower numbered vertices.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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