Answer the following about the worst-case analysis for the following graph algor

Question

Answer the following about the worst-case analysis for the following graph algorithm: Input: G = (V, E): graph with n vertices and m edges Input: n, m: order and size of G, respectively 1 Algorithm: GraphMystery 2 q= Queue() 3 visited= Array(nm) 4 Initialize visited to false 5 Enqueue the ordered pair (vo, Vo) on q 6 visited|0,0]=1 7 while q not empty do (vi, uj) = q. Dequeue() 9for vz N(vi) do for vy E N(vj) do 10 if . visited|x,y] then q.Enqueue(vx, vy) visited[z, y] true 12 13 14 15 16 end 17 end 18 if all entries in visited are true then 19 20 else 21return false 22 end end end return true

Explanation / Answer

In an adjacency list data structure reporting a list of the neighbors of a given node consumes almost constant time per neighbor. Or we can say, the total time required for reporting all of the neighbors of a node ni is proportional to the degree of ni.
If we consider the a node int the graph does not have any self loop, it can have atmost n-1 edges,
so N(vi) search time using adj list should be O(n)

For vx N(vi) // O(N)
     For vy N(vi) // O(N)
          if !visited[x,y] //O(1)
               then enqueue (vx,vy) //O(1)
                visited[x,y] = true //O(1)
           end
      end
end

So the complexity is O(N2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---