Consider the following algorithm to check whether a graph defined by its adjacency matrix is...

Question

Consider the following algorithm to check whether a graph defined by its adjacency matrix is complete.

ALGORITHM GraphComplete(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 complete and 0 (false) otherwise

if n = 1 return 1 //one-vertex graph is complete by definition

else

if not GraphComplete(A[0..n − 2, 0..n − 2]) return 0

else for j ←0 to n − 2 do

if A[n − 1, j]= 0 return 0

return 1

What is the algorithm’s efficiency class in the worst case?

Robert · Accepted 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
Working:

Consider the following algorithm to check whether a graph defined by its adjacency matrix is complete. ALGORITHM GraphComplete(A[0..n − 1, 0..n − 1]) //Input: Adjacency matrix A[0..n − 1, 0..n − 1])...

Solution

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment