Теоретически, вы можете реализовать BFS только с 2 состояниями. В некоторых случаях полезно иметь 3 состояния. Два из них ниже:
Наличие трех состояний для вершин (3 цвета) полезно при расчете дерева BFS. Любое ребро от Обнаруженного (D) узла до Необнаруженного (U) узла является ребром дерева. Любое ребро от обнаруженного узла до обработанного (P) узла является задним ребром. Любое ребро от обнаруженного узла до обнаруженного узла является перекрестным ребром.
В качестве другого примера, давайте предположим, что вы писали программу для печати всех ребер ненаправленного графика. С 3 цветами (U, D, P) вы обработаете все ребра, которые идут от D до U (вы открываете новую вершину) и от D до D (вы обнаруживаете ребро между братьями и сестрами). Однако вы не будете обрабатывать ребро от D до P. Так как это будет ребро, которое BFS использовало для обнаружения узла в D. С 2 цветами вы не сможете написать такую программу, не дублируя определенные ребра.
1----2
| |
| |
3----4
BFS starting at 1:
Tree Edges: {1, 2}, {1, 3}, {3, 4}
Cross Edge: {2, 4}
Without three states you will try to process {2, 1}, {3, 1}, {4, 3}, {4, 2}