0

l - adiacency list
x - 起始顶点
dfst, q - 顶点大小的空数组

std::list <int> q;
std::vector<bool> visited(cols + 1); 
for(int i = 0; i < cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
{
    q.push_back(x); q.push_back(* i);
}
while(!q.empty())
{
    y = q.back(); q.pop_back();
    x = q.back(); q.pop_back();
    if(!visited[y])
    {
        visited[y] = true;
        if(!l[y].empty())
        for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
        {
            q.push_back(y); q.push_back(* i);
        }
        dfst[x].push_back(y);
        dfst[y].push_back(x);
    }
}

我只是不明白为什么这会给出错误的结果......我不知道你是否熟悉这个算法，但如果你熟悉，我希望你能看到这里有什么问题。

编辑：

邻接表为：
1:2, 3
2:3
3:4
4:3

MST 应该是这样的：
1: 2, 3
3: 4

但它是：
2：3
3：2、4
4：3

当前的代码是：（我在需要的地方使用了括号）：

std::list <int> q;
std::vector<bool> visited(cols + 1); 
for(int i = 0; i < cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
{
    for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
    {
        q.push_back(x); q.push_back(* i);
    }
    while(!q.empty())
    {
        y = q.back(); q.pop_back();
        x = q.back(); q.pop_back();
        if(!visited[y])
        {
            visited[y] = true;
            if(!l[y].empty())
            for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
            {
                if(!visited[*i])
                {q.push_back(y); q.push_back(* i);}
            }
            dfst[x].push_back(y);
            dfst[y].push_back(x);
        }
    }
}
4

2 回答 2

0

代码看起来有点混乱实际上我认为它首先是 BFS ..但是它的 DFS 你应该在添加到堆栈之前检查节点是否被访问（列表后面）

while(!q.empty())
{
    y = q.back(); q.pop_back();
    x = q.back(); q.pop_back();
    if(!visited[y])
    {
        visited[y] = true;
        if(!l[y].empty())
        for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
        {
            if(!visited[*i])
            {q.push_back(y); q.push_back(* i);}
        }
        dfst[x].push_back(y);
        dfst[y].push_back(x);
    }
}
于 2013-06-17T20:37:03.493 回答
0

我研究了你的代码，它似乎是正确的。但是，请记住，如果您的输入树有一个循环，则存在多个 DFS 树。您获得的树取决于您处理顶点的顺序。也许你的输入有一个循环？如果是这样，您的代码可能以与解决方案中处理节点的顺序不同的顺序处理节点。

例如，为输入树采用以下邻接表，其中节点用字母表示：

a: b,c
b: a,d
c: a,c,e
d: b,c,e
e: c,d

从a开始，如果我们根据字母顺序在邻接列表中查找下一个节点，我们会得到以下DFS树：

a: b
b: a,d
c: d,e
d: b,d
e: c

但是，使用您的算法，我们得到以下结果：

a: c
b: d
c: a,e
d: b,e
e: c,d

如果发生这种情况，也许可以尝试递归方法。

不过，查看一些示例输入和输出将有助于进一步解决这个问题，因为这可能不是您的问题。

编辑：我应该澄清一个循环图中的多个 DFS 树适用于循环是双向的，例如无向图。关键是，您可能会发现一棵 DFS 树也是正确的，但与被识别为正确的树不同。

编辑（再次）：您可能遇到的另一个问题：您的算法似乎适用于无向图，因为您dfst[x].push_back(y); dfst[y].push_back(x);的代码中有陈述，但您在示例中给出的输入图看起来像是有向图。删除第二个语句 ( dfst[y].push_back(x);) 应该更正此问题

于 2013-06-17T21:03:15.067 回答