C语言 构造一个有向无环图

Question

我正在完成一项任务，其中最后一步是采取一对数组(其中一对本质上是图中的一条边)并从中制作一个无环图。如果一对恰好在图中形成一个循环，那么应该跳过它。DAG将以邻接矩阵的形式存储(边是未加权的，因此它的类型为bool matrix[][])

我想实现一个修改DFS,基于我在网上阅读的内容。这个任务是用C编写的，我是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);

结论:一定要初始化你的变量。