Граф (1238814), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Подсчет компонентов графа. Переменная graphsize хранит размер списка вершин. Обращение к этому закрытому члену класса осуществляется посредством метода NumberOfVertices. Оператор GraphEmpty проверяет, пуст ли список.

Доступ к компонентам графа.

Компоненты графа содержатся в списке вершин и матрице смежности. Итератор вершин, являясь дружественным по отношению к классу Graph, позволяет сканировать список вершин. Этот итератор — наследник класса SeqListlterator.

template <class T>

class Vertexlterator: public SeqListIterator<T>

{

public:

Vertexlterator(Graph<T>& G) ;

};

Конструктор просто инициализирует базовый класс для прохождения списка вершин vertexList.

template <class T>

VertexIterator<T>::Vertexlterator(Graph<T>& G):

SeqListIterator<T> (G.vertexList)

{}

Итератор сканирует элементы vertexList и используется для реализации функции GetVertexPos, которая осуществляет сканирование списка вершин и возвращает позицию вершины в этом списке.

template <class T>

int Graph<T>::GetVertexPos(const T& vertex)

{

SeqListIterator<T> liter(vertexList);

int pos * 0;

while(!liter.EndOfList () && liter.Data() !« vertex)

{

pos++;

liter.Next();

}

return pos;

}

Метод GetWeight возвращает вес ребра, соединяющего vertexl и vertex2. Чтобы получить позиции этих двух вершин в списке, а следовательно, и строку со столбцом в матрице смежности, используется функция GetVertexPos. Если любая из двух вершин отсутствует в списке вершин, метод возвращает -1. Метод GetNeighbors создает список вершин, смежных с vertex. Этот список является выходным параметром и может быть просканирован с помощью итератора последовательных списков. Если vertex не имеет смежных вершин, метод возвращает пустой список.

// возвратить список смежных вершин

template <class T>

SeqList<T>fi Graph::GetNeighbors(const T& vertex)

{

SeqList<T> *L;

SeqListIterator<T> viter(vertexList);

// создать пустой список

L = new SeqList<T>;

// позиция в списке, соответствующая номеру строки матрицы смежности

int pos = GetVertexPos(vertex);

// если вершины vertex нет в списке вершин, закончить

if (pos -« -1)

{

cerr << "GetNeighbors: такой вершины нет в графе." << endl;

return *L; // вернуть пустой список

}

// сканировать строку матрицы смежности и включать в список все вершины, c ребром ненулевого веса // из vertex

for (int i=0; Kgraphsize; i++)

{

if (edge[pos][i] > 0)

L->lnsert(viter.Data() ) ;

viter.Next();

}

return *L;

}

Метод Delete Vertex класса Graph удаляет вершину из графа. Если вершины нет в списке, выдается сообщение об ошибке и осуществляется возврат управления. В противном случае удаляются все ребра, соединяющие удаляемую вершину с другими вершинами. При этом в матрице смежности должны быть

скорректированы три области. Поэтому эта операция выполняется за время 0(п2), так как каждая область является частью матрицы n x п.

// удалить вершину из списка вершин и скорректировать матрицу

// смежности, удалив принадлежащие этой вершине ребра

template <class T>

void Graph<T>::DeleteVertex(const T& vertex)

{

// получить позицию вершины в списке вершин

int pos = GetVertexPos(vertex);

int row, col;

// если такой вершины нет, сообщить об этом и вернуть управление

if (pos == -1)

{

cerr « "DeleteVertex: вершины нет графы" « endl;

return;

}

// удалить вершину и уменьшить graphsize

vertexList.Delete(vertex);

graphsize--;

// матрица смежности делится на три области

for (row=0; row<pos; row++) // область I

for (col=pos+l; col<graphsize; col++)

edge[row][col-1] = edge[row][col];

for (row=pos+l; row<graphsize; row++) // область II

for (col=pos+l; col<graphsize; col++)

edge[row-1][col-1] = edge[row][col];

for (row=pos+l; row<graphsize; row++) // область III

for {col=0; col<pos; col++)

edge[row-1][col] = edge[row][col];

}

Удаление ребра производится путем удаления связи между двумя вершинами. После проверки наличия вершин в vertexList метод DeleteEdge присваивает данному ребру нулевой вес, оставляя все другие ребра неизменными. Если такого ребра нет в графе, процедура выдает сообщение об ошибке и завершается.

Способы прохождения графов

Поиск "сначала в глубину". Для хранения обработанных вершин используется список L, а для запоминания смежных вершин — стек S. Поместив

// начиная с начальной вершины, сформировать список вершин,

// обрабатываемых в порядке обхода "сначала в глубину"

template <class T>

SeqList <T> & Graph<T>::DepthFirstSearch{const T& beginVertex)

{

// стек для временного хранения вершин, ожидающих обработки

Stack<T> S;

// L - список пройденных вершин. adjL содержит вершины, смежные с текущей. L создается динамиче

// ски, поэтому можно возвратить его адрес

SeqList<T> *L, adjL;

// iteradjL - итератор списка смежных вершин

SeqListIterator<T> iteradjL(adjL);

Т vertex;

// инициализировать выходной список. поместить начальную вершину в стек

L = new SeqList<T>;

S.Push(beginVertex);

// продолжать сканирование, пока не опустеет стек

while (IS.StackEmpty())

{

// вытолкнуть очередную вершину

vertex = S.PopO ;

// проверить ее наличие в списке L

if (!FindVertex(*L, vertex))

{

// если нет, включить вершину в L,

//а также получить все смежные с ней вершины

(*L).Insert(vertex);

adjL = GetNeighbors(vertex);

// установить итератор на текущий adjL

iteradjL.SetList(adjL);

// сканировать список смежных вершин. помещать в стек те из них, которые отсутствуют в списке L

for (iteradjL.Reset(); !iteradjL.EndOfList()/ iteradjL.Next())

if (!FindVertex(*L, iteradjL.Data()))

S.Push(iteradjL.Data());

}

}

// возвратить выходной список

return *L;

}

17

Характеристики

Список файлов семинаров