Поиск в глубину у графа

Поиск в глубину - это метод прохода графа, когда просматривается еще не пройденная вершина, потом происходит проход по смежным вершинам, затем когда остаются не иследованные ребра, происходит возврат в вершину. Алгоритм работает до тех пор, пока не будут открытые все вершины, достижимые из исходной.
Сам алгоритм:
Он состоит из 2 ух процедур:

1. DFS(G) - нужна для инициализации всех переменных и цикла для прохода по всем вершинам
2. DFS_VISIT(u) - где u - вершина, которую нужно посетить. Эта процедура обработки вершина, где проиходит окраска каждой вершины, обозначения времени открытия и закрытия вершины (закрытие - окраска в черный цвет, открытие - окраска в серый цвет).

DFS(G)

Для каждой вершины u из множества вершин Графа

Окрасить в белый цвет

Инициализировать счетчик времени нулем
Для каждой вершины u из множества вершин Графа

Если вершина окрашена в белый, т.е. не пройдена

Посетить ее, т.е. запустить процедуру DFS_VISIT(u)

DFS_VISIT(u)

Окрасить вершину в серый цвет
Увеличить счетчик времени time++
Обозначить время открытия d[u]=time
Для каждой вершины v смежной нашей вершине u

Если вершина v окрашена в белый, т.е. не пройдена

Обозначить u как вершину предшествующую вершине v
Рекурсивно вызвать процедуру обработки для v: DFS_VISIT(v)


Окрасить вершину u в черный цвет
Обозначить время закрытия f[u]=time=time+1

Использующиеся данные:

Глобальная область видимости:

vector<unsigned int> color; //вектор цветов, 0 - белый, 1 - серый, 2 - черный

vector<unsigned int> predcessors; //вектор предшественников, если хотите построить дерево глубины

vector<unsigned int> d; //вектор к-ый хранит время открытия вершины

vector<unsigned int> f;  //вектор к-ый хранит время закрытия вершины

unsigned int timer; //таймер

ConnectionMatrix-матрица смежности графа

Реализация процедуры DFS:

void DFS (unsigned int NumOfVertices, double **ConnectionMatrix){

color.assign(NumOfVertices,0); //инициализация всех векторов

predcessors.resize(NumOfVertices);

d.resize(NumOfVertices);

f.resize(NumOfVertices);

timer=0; //обнуляем таймер

for (int u=0; u<NumOfVertices; u++){

if (color[u]==0) //если не пройденна - посетить

DFS_VISIT(u, ConnectionMatrix, NumOfVertices);

}

}

Реализация DFS_VISIT:

void DFS_VISIT(unsigned int u, double **ConnectionMatrix, unsigned int NumOfVertices){

color[u]=1; //теперь вершина окрашена в серый

timer++; //увеличим время

d[u]=timer; //время открытия

for (unsigned int v=0; v<NumOfVertices; v++){

if (ConnectionMatrix[u][v])

if (color[v]==0){

predcessors[v]=u;

DFS_VISIT(v, ConnectionMatrix, NumOfVertices); //рекурсивынй вызов для                       вершины v

}

}

color[u]=2; //покрасим в черный

f[u]=timer=timer+1; //обозначим время закрытия вершины u

}

Posted in: Алгоритмы, Графы, CPP