计算圆圈中权重的乘积(图形)

Question

我有一个有向图，它有0个或更多的圆圈。我想知道圆圈内权重的最大乘积是否超过阈值。

例：

--------->
^        |1
0.5     | <------v
1 -----------> 2 
^             |
|4            |1
|     2       v
4<------------3

此图有 4 条边和 2 个圆。第一个圆 (2 -> 2) 的乘积为 1。第二个圆 (1 -> 2 -> 3 -> 4 -> 1) 的乘积为 4。如果乘积大于 1，则算法输出 true，否则将输出 false。此图的输出为 true。

我的方法：

• 我正在使用带有邻接列表的图形
• 我正在使用这个基于 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";
}
}

Answer 1

这是对这个问题的部分回答。只要阈值等于 1，它就会工作。

使用贝尔曼福特检测产品超过阈值的周期