更改

It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.

It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.

可以使用'''<font color="#ff8000"> 深度优先搜索Depth-first search</font>'''来测试图是否为二分图，并在线性时间内返回双色（如果是二分图）或奇数环（如果不是二分图）。其方法的主要思想是为每个顶点分配与'''<font color="#ff8000"> 深度优先搜索林Depth-first search forest</font>'''中其父级颜色不同的颜色，并在其中进行遍历。这必定会为'''<font color="#ff8000"> 生成森林Spanning forest</font>'''提供两种颜色，包括将顶点连接到其父级的边。不过它可能无法为非森林边正确着色。在深度优先搜索林中，每个非林边缘的两个顶点之一是另一个顶点的祖先，并且当深度优先搜索发现这种类型的边时，应检查这两个顶点是否具有不同的颜色。如果不是，则森林中从祖先到后代的路径与颜色不同的边一起会形成一个奇数环，该奇数环会从算法中返回，并输出非二分图的结果。但是，如果算法在未检测到此类奇数环的情况下终止，则必须对每个边进行适当的着色，并返回双色以及该图形为二分图的结果。

可以使用'''<font color="#ff8000"> 深度优先搜索Depth-first search</font>'''来测试图是否为二分图，并在线性时间内返回双色（如果是二分图）或奇数环（如果不是二分图）。其方法的主要思想是为每个顶点分配与'''<font color="#ff8000"> 深度优先搜索丛Depth-first search forest</font>'''中其上级颜色不同的颜色，并在其中进行遍历。这必定会为'''<font color="#ff8000"> 生成森林Spanning forest</font>'''提供两种颜色，包括将顶点连接到其上级的边。不过它可能无法为非森林边正确着色。在深度优先搜索林中，每个非林边缘的两个顶点之一是另一个顶点的始源，并且当深度优先搜索发现这种类型的边时，应检查这两个顶点是否具有不同的颜色。如果不是，则森林中从始源到后代的路径与颜色不同的边一起会形成一个奇数环，该奇数环会从算法中返回，并输出非二分图的结果。但是，如果算法在未检测到此类奇数环的情况下终止，则必须对每个边进行适当的着色，并返回双色以及该图形为二分图的结果。