计算圆中权重的乘积（图） [英] Calculate product of weights in circle (graph)
本文介绍了计算圆中权重的乘积（图）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个有向图，它有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，否则会输出错误。该图的输出是真实的。
我的方法：
- 我正在使用带有邻接列表的图
- 我正在使用 算法，它基于 DFS ，检测
个周期 - 与GeeksForGeeks的算法不同，在第一个循环之后，我不停下来，因为我想找到具有最大权重产品的循环
- 找到一个循环后，我从递归堆栈中删除所有不属于循环的节点
- 我使用堆栈中剩余的节点来计算产品
你能帮我在下面的代码中找到错误吗？ 我的b
$ b
我的代码：
#include >
#include< list>
#include< limits.h>
#include< vector>
使用namespace std;
类图
{
int V; //顶点数
list< pair< int，double>> *调整; //指向包含相邻列表的数组的指针
vector< double> isCyclicUtil（int v，bool visited []，bool * rs）; //由isCyclic（）使用
public：
Graph（int V）; //构造函数
void addEdge（int v，int w，double rate）; //添加一条边到图
bool isCyclic（）; //如果图中有一个循环，则返回true
};
Graph :: Graph（int V）
{
this-> V = V;
adj =新列表< pair< int，double>> [V];
}
void图形:: addEdge（int v，int w，double rate）
{
adj [v] .push_back（make_pair（w，rate） ）; //将w添加到v的列表中。
}
vector< double> Graph :: isCyclicUtil（int v，bool visited []，bool * recStack）
{
if（visited [v] == false）
{
//标记当前节点作为访问和递归堆栈的一部分
visited [v] = true;
recStack [v] = true;
//对与该顶点相邻的所有顶点
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）
{
//是循环
double newValue = tmp [2]; （（* i）.first！= tmp [1]）$ b $ b {
newValue = tmp [2] *（* i）.second;
}
返回向量< double> {1，tmp [1]，newValue};
else if（recStack [（* i）.first]）
{
//找到循环，节点在第一位，重量在第二位
返回向量< double> {1，（double）（* i）.first，（* i）.second};
}
}
}
//从递归堆栈中移除顶点
recStack [v] = false;
返回向量< double> {0，-1，-1};
}
//如果图形包含一个循环，则返回true，否则返回false。
//此函数是https://www.geeksforgeeks.org/archives/18212
中DFS（）的变体bool Graph :: isCyclic（）
{
/ /将所有的顶点标记为未访问且不是递归的一部分
// stack
bool * visited = new bool [V];
bool * recStack = new bool [V];
for（int i = 0; i< V; i ++）
{
visited [i] = false;
recStack [i] = false;
}
//调用递归帮助函数检测不同
// DFS树中的循环
for（int i = 0; i
vector< double> tmp = isCyclicUtil（i，visited，recStack）;
if（tmp [2]> 1）
{
return true;
}
}
返回false;
}
int main（）
{
图g（）;
//将边添加到图
if（g.isCyclic（））
{
cout<< 真正;
}
else {
cout<< 假;
$ div $解析方案 是对这个问题的部分回答。这是工作，每当阈值等于1.
i have a directed graph, which has 0 or more circles. I would like to know if the largest product of the weights inside the circle exceeds a threshold.
Example:
--------->
^ |1
0.5 | <------v
1 -----------> 2
^ |
|4 |1
| 2 v
4<------------3
This Graph has 4 Edges and 2 circles. The first circle (2 -> 2) has a product of 1. The second circle (1 -> 2 -> 3 -> 4 -> 1) has a product of 4. The algorithm outputs true, if the product is greater than 1, otherwise it will output false. The output for this graph is true.
My approach:
- I am using a graph with a adjacency list
- I am using this algorithm, which is based on DFS, to detect cycles
- unlike the algorithm from GeeksForGeeks, I do not stop, after the first cycle, since I would like to find the cycle with the biggest products of weights
- After finding a cycle, I remove all nodes not part of the cycle from the recursion stack
- I use the nodes left over on the stack to calculate the product
Can you help me find the error in the following code?
My Code:
#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";
}
}
解决方案
Here is a partial answer to the question. It is working, whenever the threshold is equal to 1.
Using Bellman Ford to detect cycles with product exceeding threshold
这篇关于计算圆中权重的乘积（图）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
