Некоторые методы обхода неориентированных графов:

1. Поиск в глубину. 14 Когда возможные пути по рёбрам, выходящим из вершин, разветвляются, нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными). 1

Алгоритм поиска в глубину: 1

1. Всем вершинам графа присваивается значение непосещённая. 1 Выбирается первая вершина и помечается как посещённая. 1

2. Для последней помеченной как посещённая вершины выбирается смежная вершина, являющаяся первой помеченной как непосещённая, и ей присваивается значение посещённая. 1 Если таких вершин нет, то берётся предыдущая помеченная вершина. 1

3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещённые. 1

4. Поиск в ширину. 1 После посещения первой вершины посещаются все соседние с ней вершины. 1 Потом посещаются все вершины, находящиеся на расстоянии двух рёбер от начальной. 1 При каждом новом шаге посещаются вершины, расстояние от которых до начальной на единицу больше предыдущего. 1 Чтобы предотвратить повторное посещение вершин, необходимо вести список посещённых вершин. 1

Для хранения временных данных, необходимых для работы алгоритма, используется очередь. 1