у меня есть ориентированный граф, который имеет 0 или более кругов.Я хотел бы знать, превышает ли пороговое значение наибольшее весов внутри круга.
Пример:
--------->
^ |1
0.5 | <------v
1 -----------> 2
^ |
|4 |1
| 2 v
4<------------3
Этот график имеет 4 ребра и 2 круга,Первый кружок (2 -> 2) имеет произведение 1. Второй кружок (1 -> 2 -> 3 -> 4 -> 1) имеет произведение 4. Алгоритм выводит true, если произведение больше чем1, в противном случае он выдаст false.Выходные данные для этого графика верны.
Мой подход:
- Я использую граф со списком смежности
- Я использую этот алгоритм, основанный на DFS , для обнаружения циклов
- в отличие от алгоритма от GeeksForGeeks, я не останавливаюсь после первого цикла, так как я хотел бы найти цикл с самыми большими произведениями весов
- После нахождения цикла я удаляю все узлы, не являющиеся частью цикла, из стека рекурсии.
- . Я использую узлы, оставшиеся в стеке, чтобы вычислить произведение* Можете ли вы помочь мне найти ошибку в следующем коде?
Мой код:
#include <iostream>
#include <list>
#include <limits.h>
#include <vector>
using namespace std;
class Graph
{
int V; // No. of vertices
list<pair<int, double>> *adj; // Pointer to an array containing adjacency lists
vector<double> isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()
public:
Graph(int V); // Constructor
void addEdge(int v, int w, double rate); // to add an edge to graph
bool isCyclic(); // returns true if there is a cycle in this graph
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<pair<int, double>>[V];
}
void Graph::addEdge(int v, int w, double rate)
{
adj[v].push_back(make_pair(w, rate)); // Add w to v’s list.
}
vector<double> Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if (visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;
// Recur for all the vertices adjacent to this vertex
list<pair<int, double>>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
if (!visited[(*i).first])
{
vector<double> tmp = isCyclicUtil((*i).first, visited, recStack);
if (tmp[0] == 1)
{
// is cycle
double newValue = tmp[2];
if ((*i).first != tmp[1])
{
newValue = tmp[2] * (*i).second;
}
return vector<double>{1, tmp[1], newValue};
}
}
else if (recStack[(*i).first])
{
// found cycle, with at node first and weight second
return vector<double>{1, (double)(*i).first, (*i).second};
}
}
}
// remove the vertex from recursion stack
recStack[v] = false;
return vector<double>{0, -1, -1};
}
// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for (int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different
// DFS trees
for (int i = 0; i < V; i++)
{
vector<double> tmp = isCyclicUtil(i, visited, recStack);
if (tmp[2] > 1)
{
return true;
}
}
return false;
}
int main()
{
Graph g();
// add edges to graph
if (g.isCyclic())
{
cout << "true";
}
else {
cout << "false";
}
}