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