1 
    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

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

4

1 回答 1

5

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

使用 Union-Find 发现 Cycles 的背景

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

它的工作原理如下：

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

“父”：是两个无向节点之间的任意指定。我们武断地说，一个是另一个的父母，反之亦然。

  • 起初，没有节点有父节点（其哨兵值-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 的边存储在左侧。您可以维护一个排序的边列表，并且不要插入重复的边（使用 a 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;
}

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

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

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

然后它正确地报告了一个循环！

于 2017-03-28T20:06:28.917 回答