CODEWITHSUNDEEP
algorithmdata-structures
Salem Alqahtani
Salem Alqahtani

Reputation: 57

Do I have to implement Adjacency matrix with BFS?

I am trying to implement BFS algorithm using queue and I do not want to look for any online code for learning purposes. All what I am doing is just following algorithms and try to implement it. I have a question regarding for Adjacency matrix (data structure for graph).

I know one common graph data structures is adjacency matrix. So, my question here, Do I have to implement Adjacency matrix along with BFS algorithm or it does not matter.

I really got confused. one of the things that confused me, the data for graph, where these data should be stored if there is not data structure ?

Sincerely

Upvotes: 0

Views: 626

Answers (2)

Gene
Gene

Reputation: 46960

The best way to choose data structures is in terms of the operations. With a complete list of operations in hand, evaluate implementations wrt criteria important to the problem: space, speed, code size, etc.

For BFS, the operations are pretty simple:

Set<Node> getSources(Graph graph) // all in graph with no in-edges
Set<Node> getNeighbors(Node node) // all reachable from node by out-edges

Now we can evaluate graph data structure options in terms of n=number of nodes:

  • Adjacency matrix:
    • getSources is O(n^2) time
    • getNeighbors is O(n) time
  • Vector of adjacency lists (alone):
    • getSources is O(n) time
    • getNeighbors is O(1) time
  • "Clever" vector of adjacency lists:
    • getSources is O(1) time
    • getNeighbors is O(1) time

The cleverness is just maintaining the sources set as the graph is constructed, so the cost is amortized by edge insertion. I.e., as you create a node, add it to the sources list because it has no out edges. As you add an edge, remove the to-node from the sources set.

Now you can make an informed choice based on run time. Do the same for space, simplicity, or whatever other considerations are in play. Then choose and implement.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372814

Breadth-first search assumes you have some kind of way of representing the graph structure that you're working with and its efficiency depends on the choice of representation you have, but you aren't constrained to use an adjacency matrix. Many implementations of BFS have the graph represented implicitly somehow (for example, as a 2D array storing a maze or as some sort of game) and work just fine. You can also use an adjacency list, which is particularly efficient for us in BFS.

The particular code you'll be writing will depend on how the graph is represented, but don't feel constrained to do it one way. Choose whatever's easiest for your application.

Upvotes: 2

Related Questions