2014-02-02
3604
Остов графа – это подграф графа, содержащий все его вершины и являющийся деревом.
Приведем пример графа и одного из его остовов:
Обходы всех вершин графа совершаются как обход некоторого его остова. Методами обхода графа являются поиск в глубину и поиск в ширину.
Алгоритм поиска в глубину: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.
Пример графа и поиска в глубину этого графа:
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 и т. д.
Пример графа и поиска в ширину этого графа:
