l - список adiacency
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);
}
}
}
