Есть класс, который описывает узел графа и класс, описывающий сам граф
Надо найти все пути из всех вершин в любую через рекурсию (именно через рекурсию!!! так поставлена задача!!!, в моей программе это функция join) и хранить их в таком виде: номер узла(до которого идем), номер соседа(через которого идет путь), количество шагов
Так вот я написал эту функцию, НО! она не так быстро работает как мне надо. Мне нужно, чтобы она работала для графа со 100 узлами (так НУЖНО). А у меня работает достаточно быстро только для 12 узлов
Вот примерный код (привожу пример только этой функции join и метода poisk, которые вызывает функцию join для всех вершин)
Код:
const int TOTALNODES = 11; //количество узлов
const int TTL = 10; //максимальная длина пути
struct map { int end; int start; int steps; }; //для таблицы маршрутизации
class Node;
struct marshrut {Node * zveno; }; //для хранения путей в графе
//используеться для поверки вхождение вершины графа в маршрут road
bool operator==(const marshrut & m1, const marshrut & m2)
{
if (m1.zveno == m2.zveno)
return true;
return false;
}
//класс, описывающий узел графа
class Node
{
private:
Node * partners[TOTALNODES-1]; //хранит адреса соседей узла (признак конца NULL)
int id; //номер узла
vector<map> routetable; //таблица маршрутизации
public:
Node() {}
~Node() {}
//поиск всех путей до вершниы this для вершин node1 через соседа node2
void join(Node & node1, Node & node2, int ttl, vector<marshrut> road);
};
//класс, описывающий граф
class Graf
{
private:
Node Nodes[TOTALNODES]; //хранит все узлы графа
public:
Graf();
~Graf() {}
void poisk();
};
void Node::join(Node & node1, Node & node2, int ttl, vector<marshrut> road)
{
//node1 - для какого узла, node2 - через какого соседа
//не нашли путь
if (ttl < 0)
return;
if (this != &node1)
{
//добавляем вершину в маршрут road
marshrut tmp;
tmp.zveno = &node1;
//tmp.end = &node2;
road.push_back(tmp);
//добавляем маршрут в таблицу маршрутизации
map temp;
//в какую вершину
temp.end=this->id;
//за сколько шагов нашли путь
temp.steps = TTL - ttl;
//через какую вершину нашли путь
temp.start = node2.id;
//добавляем в талицу маршрутизации
node1.routetable.push_back(temp);
}
//просматриваем пути через соседей node1
for (int i = 0; i < TOTALNODES-1 && node1.partners[i]; i++)
{
//для проверки вершины в маршруте road
marshrut tmp;
//tmp.start = &node1;
tmp.zveno = node1.partners[i];
//если возвращаемся в начальный узел или если пытаемся пройти по вершине второй раз
if (this == node1.partners[i] || road.end() != find(road.begin(),road.end(),tmp))
continue;
join(*node1.partners[i],node1,ttl-1,road);
}
}
void Graf::poisk()
{
vector<marshrut> m;
for (int i = 0; i < TOTALNODES; i++)
{
Nodes[i].join(Nodes[i],Nodes[i],TTL,m);
cout<<"Node "<<i<<" OK"<<endl;
}
}
