Остов графа. Поиск в глубину и поиск в ширину.

Остов графа – это подграф графа, содержащий все его вершины и являющийся деревом.

Приведем пример графа и одного из его остовов:

Обходы всех вершин графа совершаются как обход некоторого его остова. Методами обхода графа являются поиск в глубину и поиск в ширину.

Алгоритм поиска в глубину: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Пример графа и поиска в глубину этого графа:

1-2-3-4-3-5-3-2-1-6-7-6-8-6-9-10-11-10-9-12-9-6-1.

Порядок поиска в ширину: началу обхода приписывается метка 0; вершинам, смежным с вершинами метки i, – метка i+1 (i=0,1,2,…). Затем нумеруем вершины: вначале вершины с меткой 0, затем с меткой 1 и т. д.

Пример графа и поиска в ширину этого графа: