Итераторы

Итераторы являются, можно сказать, указателями на переменную. Они знают, где находится необходимая нам переменная и могут "добыть" её из памяти. Итераторы в основном используются для операция с элементами контейнеров: сортировка, поиск, копирование и т.д. Для создание итератора необходимо написать имя контейнера <тип данных> :: iterator и имя итератора.

Например,

vector <float>::iterator begin;

string::iterator end,cur;

Да, да. Строки это тоже контейнеры;)

Теперь что мы можем делать с итераторами.

Мы можем получить элемент, на который они ссылаются:

cout<<*cur<<endl;

. Здесь мы выводим элемент, на который указывает cur. Как вы наверное уже поняли, оператор * позволяет нам обращаться не к итераторы, а к элементу

Мы можем перейти к итераторы на следующий элемент или даже дальше:

cur++; // перейти к следующему элементу

cur+=10; // <=>cur=cur+10 перейти на 10 элементов вперед

Вот, например, вывод всего вектора на экран:

vector <string> test;

//как-то его заполнили

vector<string>::iterator cur;

for (cur=test.begin();cur<test.end();cur++)

cout<<*cur<<endl;

Приведем текст процедуры обхода в глубину. Как видно, он очень короткий и простой:

procedure dfs(v:integer);

var

i:integer;

begin

used[v]:=true;

for i:=1 to n do

if (a[v,i]=1)and(not used[i]) then

dfs(i);

end;

Поиск в ширину

Заведем очередь. Изначально поместим в очередь один элемент - начальную вершину. На каждом шаге алгоритма извлекаем из очереди одну вершину. Затем перебираем всех соседей данной вершины и добавляем их в очередь. Алгоритм заканчивается, когда очередь опустеет. Для работы с очередью в Delphi можно взять массив, с отметками начала и конца очереди, или можно взять класс TQueue из модуля Contnrs, создать объект класса TQueue можно так:

Var q:TQueue;

A:integer=6;A:^integer;

Begin

New(A); A^:=6;

Q:=TQueue.create;

Q.push(A);

while Q.count>0 do A:=Q.pop;

end;

Для работы в C++ можно взять массив, с отметками начала и конца очереди, или воспользоваться шаблонным типом queue<>, реализующим очередь. Для этого надо подключить заголовочный файл <queue.h>:

queue<int> s; int a=5;

s.push(a);

while (!s.empty()) {

a=s.front();

s.pop();

cout<<a<<endl;

}

Топологическая сортировка

Топологической сортировкой называют порядок нумерации вершин ориентированного графа, при котором любое ребро идет из вершины с меньшим номером в вершину с большим.

Очевидно, что не любой граф можно отсортировать топологически. Можно доказать, что топологическая сортировка существует для ациклических графов и не существует для циклических.

Итак, займемся построением топологической сортировки. Предположим, что граф ацикличен, т.е. решение существует. Что делает обход в глубину? При запуске из какой-то вершины v он пытается запуститься вдоль всех рёбер, исходящих из v. Вдоль тех рёбер, концы которых уже были посещены ранее, он не проходит, а вдоль всех остальных — проходит и вызывает себя от их концов.

Таким образом, к моменту выхода из вызова dfs(v) все вершины, достижимые из v как непосредственно (по одному ребру), так и косвенно (по пути) — все такие вершины уже посещены обходом. Следовательно, если мы будем в момент выхода из dfs(v) добавлять нашу вершину в начало некоего списка, то в конце концов в этом списке получится топологическая сортировка.

Остов графа

Такой подграф можно построить с помощью алгоритма поиска любого вида. Для этого во время поиска параллельно строится новый граф: если найдена новая еще непомеченная вершина u в списке инцидентности вершины v, то ребро (v,u) добавляется в строящийся граф. Если исходный граф - несвязный, то задача не имеет решения. Для связного исходного графа получим, что построенный граф является связным, так как новые ребра достраиваются к уже просмотренным вершинам, которые между собой связаны. Этот граф не содержит циклов, так как в него не добавляется ребро оба конца которого просмотрены, то есть связаны маршрутом. Следовательно, построенный граф является деревом.