制作有向无环图

Question

我正在执行一项任务，其中最后一步是获取一对数组（其中一对本质上是图中的一条边）并从中制作一个无环图。如果一对碰巧在图中创建了一个循环，那么应该跳过它。 DAG 将存储为邻接矩阵（边未加权，因此它的类型为 bool matrix[][] ）

我尝试根据在线阅读的内容实施修改后的 DFS。任务是用 C 语言编写的，我是该语言的新手，对于代码的粗略之处深表歉意。关键是它不会跳过循环形成对，我被困在这一点上。感谢任何建议或帮助。

    int MAX; //number of nodes in the graph
    int player; //a node in the graph
    typedef struct
    {
        int winner;
        int loser;
    } pair;         //a directed edge from player 'winner' to player 'loser'

    pair pairs[MAX * (MAX - 1) / 2];   //array of all valid pairs

int main(void)
{
    /* Get input from console for:
            MAX - desired number of players, <= 9,
        . . .
        int results[MAX][MAX]; - a table (2D array), where each element
        results[A][B] shows the number of wins that player A
        has over player B, and vice versa.
        Element results[X][X] = 0 always.
        A new pair is only added when two players have unequal
        number of wins over each other: results[A][B] != results[B][A],
        so that pairs[i].winner is the one having more wins than losses
        against pairs[i].loser .
        pairs[] is then sorted in descending order according to 
        the value of pairs[i].winner .

    
        The goal is to create another 2D array
        bool matrix[MAX][MAX];
        by adding each pair in pairs[] sequentially,
        so that matrix[][] is the adjacency matrix of a
        Directed Acyclic Graph. (a.k.a. if a pair happens to create 
        a cycle, it must not be added)

    */
    
    DAG();
}

    void DAG(void)
    {
    int from, to;

    for (int i = 0; i < pair_count; i++)
    {
        //Create an edge in graph
        from = pairs[i].winner;
        to = pairs[i].loser;
        matrix[from][to] = true;

        //Check if this edge made a cycle
        bool visited[MAX];
        bool onStack[MAX];
        if (cyclicGraph(visited, onStack))
        {
            matrix[from][to] = false;
        }

        //Here we should have the DAG in locked
        return;
    }

    bool cyclicGraph(bool visited[], bool onStack[])
    {
        for (int k = 0; k < MAX; k++)
        {
            //Run the hasCycle-DFS only from unvisited vertices
            if (!visited[k] && hasCycle(k, visited, onStack))
            {
                //if it forms a cycle,
                return true;
            }
        }
        return false;
    }

    bool hasCycle(int x, bool visited[], bool onStack[])
    {
        // we push this 'x' node onto the stack
        onStack[x] = true;

        int child;
        for (int i = 0; i < MAX; i++)
        {
            if (locked[x][i])       //x's children are only i's holding True values in array "locked[x][i]"
            {
                child = i;
                if (onStack[child])
                {
                    return true;
                }
                if (!visited[child] && hasCycle(child, visited, onStack))
                {
                    return true;
                }
            }
        }
        //we pop the 'x' from the stack and mark it as visited
        onStack[x] = false;
        visited[x] = true;
        return false;
    }

Answer 1

过了一会儿我又回到了这个问题，我发现了这个错误。两个数组 bool visited[MAX]; bool onStack[MAX]; 保存被访问节点的信息或在 DFS 期间在递归堆栈上的信息尚未初始化。一个简单的解决方案是用假值初始化它们：

memset(visited, false, sizeof visited);
memset(onStack, false, sizeof onStack);

结论：始终确保初始化您的变量。

制作有向无环图

Making a Directed Acyclic Graph

c

algorithm

graph

directed-acyclic-graphs