使用 find 和 Union 检测 Graph 中的循环
Detection of cycle in Graph using find and Union
int main()
{
char line[100];
int N = 5;
vector<int>adj[N];
FILE *in = fopen("test.txt", "r");
for (int i = 1; i <= N; i++) // Accepting the graph from file
{
fgets(line, 100, in);
char *pch = strtok(line, "\t \n");
int u = atoi(pch);
pch = strtok(NULL, "\t \n");
while (pch != NULL)
{
int v = atoi(pch);
adj[u-1].push_back(v);
pch = strtok(NULL, "\t \n");
}
}
for( int i = 0; i < 5; i++ ) // printing the graph
{
for( int p = 0 ; p < adj[i].size(); p++ )
{
cout<< i+1 << " , "<< adj[i][p]<<endl;
}
}
if (isCycle(adj))
cout << endl << "graph contains cycle" ;
else
cout << endl << "graph does not contain cycle" ;
return 0;
}
int isCycle( vector<int> adj[] )
{
// Allocate memory for creating V subsets
int *parent = (int*) malloc( 5 * sizeof(int) );
// Initialize all subsets as single element sets
memset(parent, -1, sizeof(int) * 5);
for(int i = 0; i < 5; i++)
{
for( int p = 0 ; p < adj[i].size(); p++ )
{
int x = find(parent,i);
int y = find(parent, adj[i][p]-1); // I think problem is here
if (x == y)
return 1;
Union(parent, x, y);
}
}
return 0;
}
// A utility function to find the subset of an element i
int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// A utility function to do union of two subsets
void Union(int parent[], int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
test.txt 文件包含以下输入：
1 2 3
2 1 4 5
3 1
4 2
5 2
第一列包含顶点 ( 1 - 5 )
1 2 3
上一行（第一行）表示，Node 1 连接到 Node 2 和 Node 3
2 1 4 5
上一行（第 2 行）表示，Node 2 连接到 Node 1、Node 4 和 Node 5
现在的问题是，接受任何输入它总是说：图形包含循环。（尽管图形不包含循环）
现在在上面的输入图中不包含循环但说图形包含循环。
我哪里错了？？谁能帮我 ？？
问题出在你的输入，但首先要了解一些背景知识：
使用 Union-Find 发现 Cycles 的背景
Union-Find 算法需要一个无向图。
它的基本工作原理如下：
- 创建一组基本上是节点 ID 对的边
- 例如
(1,2), (2,3)
- 对于每条边：
- 找到left-side的"parent"（找到部分）
- 找到right-side的"parent"（找到部分）
- 如果 parent 相同，则有一个循环
- 否则，left-side的parent现在等于右边的parent（联合部分）
"Parent"：是两个无向节点之间的任意指定。我们任意说一个是另一个的parent，反之亦然。
- 起初，没有节点有parent（
-1的标记值用于
- 然后，当您遍历边时，您将分配这些 parents
- 如果一个parent不存在，一个节点就是它自己的parent（0是0的parent，1是1的parent，等等）
- 在计算边的两侧的 parent 之后（例如
1 和 2 边 (1, 2) 我们首先会看到它们的 parent不一样（1的parent是1，2的parent是2）。
- 此时，我们联合 parent使它们相同
- 1的parent变成2，2的parent仍然是2
- 将"Union"部分视为"unioning two subsets of nodes under a common parent"，因此子集1和2变为(1, 2)，其parent为2。
但是，按照您的算法编写方式，它假设如果我们首先收到边(1, 2)，那么我们将不会 稍后接收边缘 (2, 1)。您的意见不同意。因此你有周期。
如果您删除这些冗余边并提供如下输入：
1 2 3
2 4 5
3
4
5
It will work(I C++-ified the heck out of your code here, by the way). However, otherwise it will correctly report a cycle
你的挑战
因此要考虑到您的输入与算法预期的不同。也就是说，如果边已经存在，您可能不应该创建边。
我会推荐什么：
- 由于图是无向的，因此始终将具有较小 ID 的边存储在左侧。您可以维护一个排序的边列表，并且不要插入重复的边（使用 std::set）来表示您的边列表）。
生成的代码看起来像这样（使用 cin 作为输入）：
using edge_t = std::pair<int, int>;
using edge_list_t = std::set<edge_t>;
using parent_child_map_t = std::map<int, int>;
// find the parent for an id
int find(const parent_child_map_t& idToParent, int id)
{
auto iter = idToParent.find(id);
if (iter == idToParent.end())
return id;
return find(idToParent, iter->second);
}
// lhsId and rhsId are two sides to an edge
// this Union function will determine who is the "parent"
// arbitrarily choosing the rhsId's parent as lhsId's parent
void ComputeUnion(parent_child_map_t* idToParent, int lhsId, int rhsId)
{
if (!idToParent)
return;
int xsubset = find(*idToParent, lhsId);
int ysubset = find(*idToParent, rhsId);
(*idToParent)[xsubset] = ysubset;
}
bool HasCycle(const edge_list_t& edges )
{
// determine parents
parent_child_map_t idToParent;
for (auto&& nextEdge : edges)
{
int x = find(idToParent, nextEdge.first);
int y = find(idToParent, nextEdge.second);
if (x == y)
return true;
ComputeUnion(&idToParent, x, y);
}
return false;
}
int main()
{
edge_list_t edges;
std::string nextline;
while(std::getline(std::cin, nextline))
{
std::istringstream nextLineStream(nextline);
int id;
nextLineStream >> id;
int nextNeighbor;
while(nextLineStream >> nextNeighbor)
{
int lhs = std::min(id, nextNeighbor);
int rhs = std::max(id, nextNeighbor);
edges.insert(std::make_pair(lhs, rhs));
}
}
if (HasCycle(edges))
std::cout << "Graph contains cycle\n";
else
std::cout << "Graph does not contain cycle\n";
return 0;
}
And now it no longer reports a cycle in your input!
但是，如果我们像这样提供输入（注意 (4,1) 的附加边）：
1 2 3
1 2 3
2 1 4 5
3 1
4 2 1
5 2
Then it correctly reports a cycle!
int main()
{
char line[100];
int N = 5;
vector<int>adj[N];
FILE *in = fopen("test.txt", "r");
for (int i = 1; i <= N; i++) // Accepting the graph from file
{
fgets(line, 100, in);
char *pch = strtok(line, "\t \n");
int u = atoi(pch);
pch = strtok(NULL, "\t \n");
while (pch != NULL)
{
int v = atoi(pch);
adj[u-1].push_back(v);
pch = strtok(NULL, "\t \n");
}
}
for( int i = 0; i < 5; i++ ) // printing the graph
{
for( int p = 0 ; p < adj[i].size(); p++ )
{
cout<< i+1 << " , "<< adj[i][p]<<endl;
}
}
if (isCycle(adj))
cout << endl << "graph contains cycle" ;
else
cout << endl << "graph does not contain cycle" ;
return 0;
}
int isCycle( vector<int> adj[] )
{
// Allocate memory for creating V subsets
int *parent = (int*) malloc( 5 * sizeof(int) );
// Initialize all subsets as single element sets
memset(parent, -1, sizeof(int) * 5);
for(int i = 0; i < 5; i++)
{
for( int p = 0 ; p < adj[i].size(); p++ )
{
int x = find(parent,i);
int y = find(parent, adj[i][p]-1); // I think problem is here
if (x == y)
return 1;
Union(parent, x, y);
}
}
return 0;
}
// A utility function to find the subset of an element i
int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// A utility function to do union of two subsets
void Union(int parent[], int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
test.txt 文件包含以下输入：
1 2 3
2 1 4 5
3 1
4 2
5 2
第一列包含顶点 ( 1 - 5 )
1 2 3
上一行（第一行）表示，Node 1 连接到 Node 2 和 Node 3
2 1 4 5
上一行（第 2 行）表示，Node 2 连接到 Node 1、Node 4 和 Node 5
现在的问题是，接受任何输入它总是说：图形包含循环。（尽管图形不包含循环） 现在在上面的输入图中不包含循环但说图形包含循环。 我哪里错了？？谁能帮我 ？？
问题出在你的输入，但首先要了解一些背景知识：
使用 Union-Find 发现 Cycles 的背景
Union-Find 算法需要一个无向图。
它的基本工作原理如下：
- 创建一组基本上是节点 ID 对的边
- 例如
(1,2), (2,3)
- 例如
- 对于每条边：
- 找到left-side的"parent"（找到部分）
- 找到right-side的"parent"（找到部分）
- 如果 parent 相同，则有一个循环
- 否则，left-side的parent现在等于右边的parent（联合部分）
"Parent"：是两个无向节点之间的任意指定。我们任意说一个是另一个的parent，反之亦然。
- 起初，没有节点有parent（
-1的标记值用于 - 然后，当您遍历边时，您将分配这些 parents
- 如果一个parent不存在，一个节点就是它自己的parent（0是0的parent，1是1的parent，等等）
- 在计算边的两侧的 parent 之后（例如
1和2边(1, 2)我们首先会看到它们的 parent不一样（1的parent是1，2的parent是2）。 - 此时，我们联合 parent使它们相同
- 1的parent变成2，2的parent仍然是2
- 将"Union"部分视为"unioning two subsets of nodes under a common parent"，因此子集1和2变为(1, 2)，其parent为2。
但是，按照您的算法编写方式，它假设如果我们首先收到边(1, 2)，那么我们将不会 稍后接收边缘 (2, 1)。您的意见不同意。因此你有周期。
如果您删除这些冗余边并提供如下输入：
1 2 3
2 4 5
3
4
5
It will work(I C++-ified the heck out of your code here, by the way). However, otherwise it will correctly report a cycle
你的挑战
因此要考虑到您的输入与算法预期的不同。也就是说，如果边已经存在，您可能不应该创建边。
我会推荐什么：
- 由于图是无向的，因此始终将具有较小 ID 的边存储在左侧。您可以维护一个排序的边列表，并且不要插入重复的边（使用 std::set）来表示您的边列表）。
生成的代码看起来像这样（使用 cin 作为输入）：
using edge_t = std::pair<int, int>;
using edge_list_t = std::set<edge_t>;
using parent_child_map_t = std::map<int, int>;
// find the parent for an id
int find(const parent_child_map_t& idToParent, int id)
{
auto iter = idToParent.find(id);
if (iter == idToParent.end())
return id;
return find(idToParent, iter->second);
}
// lhsId and rhsId are two sides to an edge
// this Union function will determine who is the "parent"
// arbitrarily choosing the rhsId's parent as lhsId's parent
void ComputeUnion(parent_child_map_t* idToParent, int lhsId, int rhsId)
{
if (!idToParent)
return;
int xsubset = find(*idToParent, lhsId);
int ysubset = find(*idToParent, rhsId);
(*idToParent)[xsubset] = ysubset;
}
bool HasCycle(const edge_list_t& edges )
{
// determine parents
parent_child_map_t idToParent;
for (auto&& nextEdge : edges)
{
int x = find(idToParent, nextEdge.first);
int y = find(idToParent, nextEdge.second);
if (x == y)
return true;
ComputeUnion(&idToParent, x, y);
}
return false;
}
int main()
{
edge_list_t edges;
std::string nextline;
while(std::getline(std::cin, nextline))
{
std::istringstream nextLineStream(nextline);
int id;
nextLineStream >> id;
int nextNeighbor;
while(nextLineStream >> nextNeighbor)
{
int lhs = std::min(id, nextNeighbor);
int rhs = std::max(id, nextNeighbor);
edges.insert(std::make_pair(lhs, rhs));
}
}
if (HasCycle(edges))
std::cout << "Graph contains cycle\n";
else
std::cout << "Graph does not contain cycle\n";
return 0;
}
And now it no longer reports a cycle in your input!
但是，如果我们像这样提供输入（注意 (4,1) 的附加边）：
1 2 3
1 2 3
2 1 4 5
3 1
4 2 1
5 2