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

Граф представляет собой структуру с произвольным характером связей между элементами. С точки зрения программирования наличие в элементе "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]); // Рекурсивный обход

}
}