863 views
0 votes
0 votes
How through a BFS we can find graph is connected or disconnected?

Plz give some example and explain

2 Answers

1 votes
1 votes
First have count = total no.of vertices in a graph

Starts with a Vertex do BFS traversal, in BFS traversal  decrease the count on detecting new vertex.

after getting over the BFS, check count=0 or not?

if count=0 ===> Connected otherwise not connected
1 votes
1 votes
In case of Breadth first traversal we take an VISITED array of size equal to no of vertices in the graph.Intially we put zero in array for all the nodes or vertices means no node is visited till now.Then we start BFS,as and when we visit a node put it into queue as well as make it 1 in the visited array and so on. Now when queue is empty check whether all of the element in visited array are 1 or not.If not it means all nodes are not visited and hence graph is disconnected

Related questions

1 votes
1 votes
2 answers
1
saptarshiDey asked Feb 1, 2019
821 views
What will be the path from A-H if BFS is used in the following graph?
0 votes
0 votes
0 answers
2
Tuhin Dutta asked Dec 12, 2017
362 views
Starting vertex is : $V_1$Find the BFS traversal sequence
0 votes
0 votes
1 answer
3
codingo1234 asked Nov 21, 2018
368 views
HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?
2 votes
2 votes
0 answers
4
gari asked Jan 11, 2018
618 views
what is the question asking exactly?