The Gateway to Computer Science Excellence
0 votes
155 views

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)
0
What about incidence matrix for it should also take o(1) time
0
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
198,589 comments
105,442 users