Я пишу программу, которая должна найти корневое связующее дерево в графе и все уникальные пути, соединяющие корень с другими вершинами в связующем дереве.Я пытаюсь выполнить обе операции только с одной функцией:
void Spanning_tree_finder(){
int * v=Add_edges(s1); int control=0; int size;
for(int i=0; i<_g.GetE(); i++){
if(control==0 && v[i]==1) {
s1[i]=1; control=1;
size=_v.size();
for(int j=0; j<size; j++){
if(_v[j].Getv2()==_g.GetEdge1(i)){
Path pnew=_v[j];
pnew.Setv2(_g.GetEdge2(i));
pnew.Setp(i);
_v.push_back(pnew);
};
if(_v[j].Getv2()==_g.GetEdge2(i)){
Path pnew=_v[j];
pnew.Setv2(_g.GetEdge1(i));
pnew.Setp(i);
_v.push_back(pnew);
};
};
Spanning_tree_finder();
};
};
return;
};
Ради контекста, функция строит связующее дерево итеративно, которое в конце процесса содержится в s1
, путемвзять дерево, также содержащееся в s1
, выполнить поиск всех соседних ребер с помощью функции Add_edges
и, таким образом, добавить к предыдущему дереву один из соседних ребер.Затем функция вызывается снова (обратите внимание, что Add_Edges
и Spanning_tree_finder
являются частью класса, а s1
является закрытым членом такого класса).Во время этого процесса функция также создает путь, соединяющий корень со свободной вершиной, связанной с недавно введенным смежным ребром, путем поиска предыдущего пути, соединяющего корень с непустой вершиной недавно введенного ребра и добавляя к этому путинедавно введенный край.Все пути хранятся в векторе путей, _v
.Я знаю, что это объяснение немного запутанное, но я надеюсь, что оно понятно.
Однако, есть проблема с этой функцией, так как кажется, что на каждой итерации все пути, содержащиеся в _v
, заменяются напуть, который был получен в текущей итерации.Вместо получения _v.size()
различных путей, _v
содержит _v.size()
копий одного и того же пути, и это выполняется на каждой итерации.Я не понимаю, почему это произошло, так как мне кажется, что функция никогда не обращается к ранее добавленным элементам.Я надеюсь, что проблема, как я объяснил, ясна, и я с удовольствием предоставлю дальнейшие разъяснения.
РЕДАКТИРОВАТЬ: Более конкретно, строки кода, которые я считаю проблемными, являются
for(int j=0; j<size; j++){
if(_v[j].Getv2()==_g.GetEdge1(i)){
Path pnew=_v[j];
pnew.Setv2(_g.GetEdge2(i));
pnew.Setp(i);
_v.push_back(pnew);
};
if(_v[j].Getv2()==_g.GetEdge2(i)){
Path pnew=_v[j];
pnew.Setv2(_g.GetEdge1(i));
pnew.Setp(i);
_v.push_back(pnew);
};
};
Суть проблемы в том, как pnew
вставляется в _v
.Вместо элемента pnew
, добавляемого в конце вектора, все элементы в _v
заменяются на pnew