Блог

Учитывая дерево (под деревом я подразумеваю N узлов, N-1 ребро и оно соединено), корень дерева изменяется, скажем, на r. Теперь, учитывая другой узел, допустим, t , вам нужно найти сумму всех узлов в поддереве с корнем в t. Я пытался реализовать это на c .

 std::map<int, std::vector< pair<int,int> > > map;
  

если я выполняю итерацию по векторной карте [t] , я должен убедиться, что она не переходит на путь, который ведет к r . Как бы мне это обеспечить?
Также есть ли лучший способ сохранить дерево на c , учитывая условия, при которых корень дерева может измениться? Я думаю, что так и будет, потому что карта ничего не передает о корне . 🙂

Проблема в том, что ваше дерево хранится в виде общего графика. Следовательно, для данной вершины вы не знаете, какая из дуг ведет к корню (т. Е. родительской).

Решение во многом зависит от контекста. Простым решением был бы поиск в глубину, начинающийся с r и ищущий t . Как только вы найдете t, вы также найдете родительский элемент t, и вы можете легко идентифицировать поддерево, начинающееся с t .

В качестве альтернативы вы можете начать с t и искать r . Когда вы найдете r, вы найдете родительский элемент t, и вы можете обойти все остальные дуги, чтобы найти поддерево t .

Что касается альтернативного представления графа, обычно лучше сохранить список вершин и для каждой вершины сохранить список соседних вершин, как в:

 std::map<int, std::list<int> >