The Gateway to Computer Science Excellence
0 votes

Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph?

  1. Adjacency List
  2. Adjacency Matrix
  3. Incidence Matrix
  4. None of these
in DS by (81 points) | 155 views

1 Answer

+1 vote
Adjacency matrix . just check the ijth entry and jith in the matrix entry
by Active (2.1k points)
What about incidence matrix for it should also take o(1) time
No it will not. Incidence matrix is a matrix where rows represents vertices and columns edge numbers. We dont know the label of edge between $i$ and $j$ beforehand. So to check whether an edge exists between $i$ and $j$ , we will check each column in worst case to check whether both $i^{th}$ and $j^{th}$ contain 1 in the same column. So worst case complexity will be $O(E)$ in case of incidence matrix.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,390 answers
105,442 users