Skip to main content
MathOverflow

Return to Answer

added 90 characters in body
Source Link
Travis Service
Travis Service
  • 336
  • 3
  • 9

If a graph on $n$ nodes has $n$ or more edges then it has a cycle (since trees are the acyclic graphs with the greatest number of edges and have exactly $n-1$ edges). So if your BFS ever traverses $n$ or more edges you may immediately stop and report that the graph has a cycle. Otherwise BFS terminates in $O(n)$ time as there are $n$ nodes and fewer than $n$ edges. In either case the runtime is $O(n)$.

EDIT: As Gerhard Paseman's comment points out this answer assumes an undirected graph.

If a graph on $n$ nodes has $n$ or more edges then it has a cycle (since trees are the acyclic graphs with the greatest number of edges and have exactly $n-1$ edges). So if your BFS ever traverses $n$ or more edges you may immediately stop and report that the graph has a cycle. Otherwise BFS terminates in $O(n)$ time as there are $n$ nodes and fewer than $n$ edges. In either case the runtime is $O(n)$.

If a graph on $n$ nodes has $n$ or more edges then it has a cycle (since trees are the acyclic graphs with the greatest number of edges and have exactly $n-1$ edges). So if your BFS ever traverses $n$ or more edges you may immediately stop and report that the graph has a cycle. Otherwise BFS terminates in $O(n)$ time as there are $n$ nodes and fewer than $n$ edges. In either case the runtime is $O(n)$.

EDIT: As Gerhard Paseman's comment points out this answer assumes an undirected graph.

Source Link
Travis Service
Travis Service
  • 336
  • 3
  • 9

If a graph on $n$ nodes has $n$ or more edges then it has a cycle (since trees are the acyclic graphs with the greatest number of edges and have exactly $n-1$ edges). So if your BFS ever traverses $n$ or more edges you may immediately stop and report that the graph has a cycle. Otherwise BFS terminates in $O(n)$ time as there are $n$ nodes and fewer than $n$ edges. In either case the runtime is $O(n)$.