Breadth first search

#1

is outputput of bfs depend upon the order of adding edges??

#2

No it just checks the nodes and their connections. It doesnt depend on in which order have u added the edges.

#3

i mean the output of bfs coming different for different order of adding edges…

#4

Different order but to same nodes right?
Like
2 3
1 3
and
1 3
2 3

These will give same bfs output when started the bfs from 1(COnsidering root).

#5

it is a small example for big one the bfs coming different…

#6

for example if we take (1 2) (1 3) the bfs is 1 2 3but if we add reverse then bfs is different 1 3 2

#7

Reverse as in ?

See it depends also on wether u r making bidirectional graph or unidirectional.

#8

in this case bidirectional…

#9

reverse means order of adding edge is (1 3) and then (1 2)

#10

Well it depends here because u see for 3 and 2 they have both same parent and same level. So in first case :
the adjacency list will be 1 : 2,3
and now it will be 1 : 3,2

So yes here the bfs traversal may differ.
Sorry abt my previous comment i was thinking about the overall graph because it remains the same :upside_down_face:.

#11

so how to identify graph uniquely by bfs in question what we have to do exactly if bfs is not uniqye??

#12

i didn’t understand it . can u plz rephrase it.

#13

means in above example the bfs is different for same graph so how can we uniquely say that this bfs belongs to this graph??

#14

Check element by element in both traversals. because

    1
   /  \
 2      3 
    1
  /    \ 
3       2

These 2 will produce different bfs sequence so just store them in an array and match element by element , if they are different then it will surely produce different bfs.

#15

I am asking if I have given two bfs how can I identify that it is sane graph or not??

#16

i think u cant because suppose

1
2
3 4
5
and
1
2
3 4 5

above given graphs will produce same dfs … so i dont think u can actually tell or not that it is the same graph or not.

Note: i have just written level wise nodes.

#17

Ohk thanks sir… …

#18

a little typo i wrote dfs instead of bfs …sorry :stuck_out_tongue:

#19

Yess that’s understandable because we were talking about bfs so i understood that…