IIIT PGEE 2019

Question

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

• A. Adjacency List
• B. Adjacency Matrix
• C. Incidence Matrix
• D. None of these

Answer 1

Adjacency matrix . just check the ijth entry and jith in the matrix entry

Comments

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.

Answer 2

Adjacency matrix,it actually checks the presence of edge btw two nodes

Answer 3

Adjacency matrix as it is an two dimensional array and array gives random access.

Answer 4

Option B) Adjacency Matrix is the answer , because only the entry is to be checked in the matrix corresponding to the nodes.