Поиск циклов в ориентированном графе реализован с использованием неупорядоченного мультикарты

Итак, я реализовал ориентированный граф, используя неупорядоченную мультикарту. Каждая пара в карте состоит из двух строк: вершины и смежной вершины.
Теперь я пытаюсь определить, есть ли в моем графике цикл, и если да, то насколько велик этот цикл. Это код, который я до сих пор:

int findCycle(const unordered_multimap<string,string> & connectedURLVertices, string y, string key)
{
string position;

position=y.find(key);

if(position!=string::npos)
{
return 1;
}

auto nodesToCheck=connectedURLVertices.equal_range(key);

for(auto & node : nodesToCheck)
{
int z=findCycle(connectedURLVertices,y+key,node);
}
}

Я просмотрел код на бумаге, и он кажется логически правильным, но я был бы признателен, если бы кто-нибудь взглянул и посмотрел, нахожусь ли я на правильном пути или что-то пропустил. Спасибо!

0

Решение

Для поиска циклов в графе вы должны рекурсивно спускаться по дугам от некоторого начального узла, пока не достигнете одного уже посещенного узла (вы можете построить std::set уже посещенных узлов или пометьте узлы по мере их посещения) или исчерпайте все узлы, не посещая уже посещенные узлы (отсутствие циклов). Критерий для выбора дуги можно настроить для более быстрого ее поиска или для типа поиска (сначала в глубина, поиск по уровню и т. д.)

0

Другие решения


По вопросам рекламы [email protected]