1 votes 1 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? Adjacency List Adjacency Matrix Incidence Matrix None of these DS iiith-pgee graph-theory time-complexity + – manikgupta123 asked Apr 29, 2019 manikgupta123 1.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Adjacency matrix . just check the ijth entry and jith in the matrix entry pratekag answered Apr 29, 2019 pratekag comment Share Follow See all 2 Comments See all 2 2 Comments reply Kaluti commented May 22, 2019 reply Follow Share What about incidence matrix for it should also take o(1) time 0 votes 0 votes pratekag commented May 26, 2019 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Adjacency matrix,it actually checks the presence of edge btw two nodes subhradeep answered Apr 18, 2020 subhradeep comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Adjacency matrix as it is an two dimensional array and array gives random access. Anup dogrial answered May 30, 2020 Anup dogrial comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Option B) Adjacency Matrix is the answer , because only the entry is to be checked in the matrix corresponding to the nodes. Sanandan answered Sep 11, 2020 Sanandan comment Share Follow See all 0 reply Please log in or register to add a comment.