使用 find 和 Union 检测图中的循环

Question

    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

现在这里的问题是，接受任何输入它总是说：图形包含循环。（虽然图形不包含循环） 现在在上面的输入图中不包含循环但说图形包含循环。我哪里错了？？谁能帮我 ？？

Answer 1

问题在于您的input，但首先是一些背景：

使用 Union-Find 发现 Cycles 的背景

Union-Find 算法需要一个无向图。

它的工作原理如下：

• 创建一组基本上是节点 id 对的边
  • 例如 (1,2), (2,3)
• 对于每条边：
  • 找到左侧的“父”（查找部分）
  • 找到右侧的“父”（查找部分）
  • 如果父母是相同的，你有一个循环
  • 否则，左侧的父级现在等于右侧的父级（联合部分）

“Parent”：是两个无向节点之间的任意指定。我们任意说一个是另一个的父级，反之则不然。

• 起初，没有节点有父节点（使用 的哨兵值-1。
• 然后，当您遍历边时，您将分配这些父项
  • 如果父节点不存在，则节点是它自己的父节点（0 是 0 的父节点，1 是 1 的父节点，等等）
  • 在计算边缘两侧的父母之后（例如1，2对于边缘，(1, 2)我们首先会看到他们的父母是不一样的（1 的父母是 1，2 的父母是 2）。
  • 在这一点上，我们联合父母使他们相同
    • 1 的父级变为 2，而 2 的父级仍为 2
    • 将“联合”部分视为“联合一个公共父节点下的两个节点子集”，因此子集 1 和 2 变为 (1, 2)，其父节点为 2。

但是，您的算法的编写方式是假设如果我们首先收到 edge (1, 2)，那么我们以后不会收到 edge (2, 1)。你的意见不同意。因此你有周期。

如果您删除这些冗余边并提供如下输入：

1 2 3
2 4 5
3 
4  
5

它会起作用（顺便说一下，我在这里对您的代码进行了 C++ 化）。但是，否则它会正确报告一个循环

你的挑战

因此要考虑到您的输入与您的算法期望的不同。也就是说，如果边已经存在，您可能不应该创建边。

我会推荐什么： - 由于图是无向图，因此始终在左侧存储具有较小 id 的边。您可以维护一个排序的边列表，并且不要插入重复的边（使用 astd::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;
}

现在它不再报告您输入中的循环！

但是，如果我们像这样提供输入（注意 的附加边(4,1)）：

1 2 3
1 2 3
2 1 4 5
3 1
4 2 1
5 2

然后它正确报告了一个周期！