CODEWITHSUNDEEP
c++algorithmsearch
Matt Stokes
Matt Stokes

Reputation: 4958

get all the edges for a given node using an adjacency matrix

I'm looking to implement a BFS traversal using an adjacency matrix and have a question related to finding the adjacent elements in the matrix.

Is there anyway that I am able to get all the edges for a given node without having to loop over the entire row in the adjacency matrix? Or is this an inherent disadvantage for using this structure on a spare matrix?

Upvotes: 0

Views: 315

Answers (1)

Renato Ferreira Pinto Jr.
Renato Ferreira Pinto Jr.

Reputation: 46

Your interpretation is correct - the main disadvantage or using adjacency matrices is that, for most applications, you have to loop over the entire row, even when dealing with a sparse graph, in order to visit all adjacent nodes.

If you do not have a particular reason for using an adjacency matrix, then considering an adjacency list instead might be a good option.

It should be noted that nothing stops you from maintaining both data structures concurrently; even though I haven't seen many cases in which that was useful, you could certainly maintain the adjacency matrix for O(1) queries on whether an edge exists or not, and the adjacency list for linear queries over all the edges leaving a given node (linear on the number of those edges).

Depending on what information you need exactly, maintaining just the degree of each node (the number of edges incident to the node) might also help - this data "comes for free" if you implement an adjacency list, but you might find that you only need the degree after all.

Upvotes: 1

Related Questions