Информатика и технология программирования

       

Структуры данных с произвольными связямиГрафы


Граф представляет собой структуру с произвольным характером связей между элементами. С точки зрения программирования наличие в элементе "A" указателя на элемент "B" соответствует наличию в графе дуги, направленной от "A" к "B". Тогда для неориентированного графа требуется наличие как прямого, так и обратного указателя. Процедуры работы с графом также могут предусматривать его рекурсивный обход. Однако при этом необходимо отмечать уже пройденные вершины для исключения зацикливания алгоритма. В приведенном ниже примере каждая вершина графа имеет счетчик проходов, который проверяется каждый раз при входе в вершину.


//------------------------------------------------------bk55-10.cpp


//------Рекурсивный обход графа


struct graph
{
int cnt; // Счетчик обходов вершин


graph **pl; // Динамический массив


}; // указателей


void ScanGraph(graph *p)
{ int i;
p-&#62cnt++; // Увеличить счетчик


for (i=0; p-&#62pl[i] !=NULL; i++)
{
if (p-&#62pl[i]-&#62cnt !=p-&#62cnt) // Вершина не просмотрена


ScanGraph(p-&#62pl[i]); // Рекурсивный обход


}
}



Содержание раздела