更改

Alternatively, a similar procedure may be used with [[breadth-first search]] in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their [[lowest common ancestor]] forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.<ref>{{citation

Alternatively, a similar procedure may be used with [[breadth-first search]] in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their [[lowest common ancestor]] forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.

Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.

Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.

For the [[intersection graph]]s of <math>n</math> [[line segment]]s or other simple shapes in the [[Euclidean plane]], it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation

For the [[intersection graph]]s of <math>n</math> [[line segment]]s or other simple shapes in the [[Euclidean plane]], it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.

For the intersection graphs of <math>n</math> line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation

For the intersection graphs of <math>n</math> line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.

对于n个线段的相交图或欧几里得平面Euclidean plane中的其他简单形状图，即使图本身可能具有多达O(N2)个边缘，也可以测试其是否而二分图，并在时间O(n lon n)中返回双色（判定为二分图）或奇数环（判定为非二分图）。

对于n个线段的相交图或欧几里得平面Euclidean plane中的其他简单形状图，即使图本身可能具有多达O(N2)个边缘，也可以测试其是否而二分图，并在时间O(n lon n)中返回双色（判定为二分图）或奇数环（判定为非二分图）。