2

I am new to graph theory, and so far I have learned only BFS and Disjoint sets in graph theory. If there is a cycle in a given, undirected, connected graph, can I find it using BFS ? My intention is to print all the vertices in the cycle. Thanks in advance.

odbhut.shei.chhele
  • 5,834
  • 16
  • 69
  • 109
  • 5
    Yes http://stackoverflow.com/questions/4464336/pseudocode-to-find-cycles-in-a-graph-using-breadth-first-search , and it's not circles, it's called cycles in graph :P – Mr.Anubis Jul 02 '12 at 18:13
  • sorry, i meant cycle. I have corrected it. – odbhut.shei.chhele Jul 02 '12 at 18:21
  • Do you mean an directed graph? If the graph is undirected then any link connecting two nodes forms a cycle. E.g. if you have A - B, then A - B - A is a cycle. – Alex Wilson Jul 02 '12 at 18:21
  • @AlexWilson no, i meant undirected graph. Can you please clarify. I am having the same problem as this guy named PROGRAMMER. Consider 2----1. If I start BFS from 1 I will begin by marking it as visited and add it to the queue. Then, in the while loop, I will retrieve it from the queue and mark any adjacent unvisited vertices as visited and add them to the queue. in other words, I will add 2 to the queue. Now, when I retrieve 2 from the queue, I will again consider all its adjacent vertices. In doing so, I will also consider 1 which is already visited. However, this does not indicate a cycle. – odbhut.shei.chhele Jul 02 '12 at 18:38

2 Answers2

3

Yes, if the graph is undirected, but it is very inefficient compared to DFS. If a graph was a directed graph, you'd have to remember if you visited the node or not, and also how you got there. BFS, which searches by "levels" from the origin will not be compatible with these parameters.

Monami165
  • 46
  • 2
1

In graph theory it's called Cycles and not Circles.It marks the nodes as visited and if the visited nodes are again visited it reports that it is a cycle.BTW finding cycles using D.F.S is better. You can find the codes here http://codes-at-igit.weebly.com/uploads/1/2/2/7/12272842/ideone_0sbcx.cpp

Tapasweni Pathak
  • 552
  • 4
  • 7
  • 24