CODEWITHSUNDEEP
cgraph-theorybreadth-first-search
Bob
Bob

Reputation: 375

How to find all neighbors of node if the graph is not in form of adjacency matrix?

I have tried to google BFS implementations in C but all of them seem to be expecting graph in form of adjacency matrix, and from what I have understood it enables to find out all adjacent nodes in no time.

  1. But what am I supposed to do to find out adjacent nodes if the input is in form of pair of nodes?
  2. Am i supposed to store the edges and loop through them each time I am looking for neighbours? But that sounds slow and like something dummy like me would do :( .
  3. Or am I somehow supposed to convert the input to adjacency matrix?

Example of input

{
    Nodes:
    0
    1
    2
    3
    Edges:
    0 2
    1 3
    2 3
    0 1
}

​

Pseducode

BFS (G, s)   //Where G is the graph and s is the source node
      let Q be queue.
      Q.enqueue( s )
      mark s as visited.
      while ( Q is not empty)
           v  =  Q.dequeue( )

          for all neighbours w of v in Graph G  /* <---------------------------------------- HOW? */
               if w is not visited 
                        Q.enqueue( w )             
                        mark w as visited.

from https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/

Upvotes: 1

Views: 1705

Answers (1)

John Bollinger
John Bollinger

Reputation: 181849

I have tried to google BFS implementations in C but all of them seem to be expecting graph in form of adjacency matrix, and from what I have understood it enables to find out all adjacent nodes in no time.

Well, no. An adjacency matrix allows you to find the set of adjacent nodes in a nonzero amount of time that is independent of the number of nodes. But it still takes time proportional to the number of nodes to determine what all the elements of that set are. Other representations, such as an adjacency list, can allow finding the set in the same constant time, and finding its elements in time proportional to their number (which can be much less than the total number of nodes).

  1. But what am I supposed to do to find out adjacent nodes if the input is in form of pair of nodes?

How about building an adjacency matrix or adjacency list or alternative representation, and then using it?

  1. Am i supposed to store the edges and loop through them each time I am looking for neighbours? But that sounds slow and like something dummy like me would do :( .

A flat list of edges is one possible representation. There are ways you could make such a list more efficient to work with (by sorting it and / or indexing it, for example), but whether that's actually a win depends on the problem.

  1. Or am I somehow supposed to convert the input to adjacency matrix?

If indeed you want to create an adjacency matrix, then start by creating a matrix representing all the nodes, with no edges. Read the edge list, and fill in the appropriate entry for each edge in it, or the appropriate two entries if the graph is undirected.

Upvotes: 1

Related Questions