Блог

У меня есть дерево (недвоичное, несбалансированное, без циклов), все узлы имеют флаги (зеленый=активный, красный=неактивный). Я начинаю с корневого узла, и мне нужно найти полный путь (от корня до конца), где все узлы активны. (Найти хотя бы один путь-это нормально.) В результате мне нужен путь, а не только информация, если таковая имеется.

Я думал использовать поиск по глубине, но я не могу понять, как включить фильтрацию по активному/неактивному. Есть какие-нибудь идеи?

Ваша рекурсия DFS будет иметь два базовых случая:

• Отрицательный: текущий узел не является зеленым.
• Положительный: текущий узел является зеленым листом, т. е. у него нет дочерних элементов.

Во всех остальных случаях рекурсивные вызовы должны выполняться на дочерних узлах узла. Как только положительный результат возвращается из рекурсивного вызова, этот положительный результат может быть расширен текущим узлом и немедленно возвращен, прерывая цикл.

Существует несколько способов реализации дерева, поэтому я сделал несколько вариантов в этой реализации JavaScript:

 function findGreenPath(tree, label) {  let root = tree[label];  if (!root.green) return null; // No path through none-green node  if (root.children == "") return label; // It is a leaf, start a path  for (let child of root.children) {  let path = findGreenPath(tree, child);  if (path != null) return label   path; // prepend this node to a good path  }  return null; // No path found }  // Implementation of the example tree in the question: let tree = { // Dictionary of nodes by their label  "A": {green: true, children: "BC"},  "B": {green: true, children: "DE"},  "C": {green: true, children: "FG"},  "D": {green: true, children: "HI"},  "E": {green: false, children: ""},  "F": {green: false, children: ""},  "G": {green: true, children: "J"},  "H": {green: false, children: ""},  "I": {green: true, children: ""},  "J": {green: true, children: "K"},  "K": {green: false, children: ""} };  let path = findGreenPath(tree, "A");   console.log(path); // ABDI 

Это просто. Как вы знаете, DFS может быть реализована стеком. Таким образом, мы помещаем корень дерева в стек, а затем открываем верхнюю часть стека и выталкиваем дочерние элементы выскочившего узла. Мы продолжаем этот процесс до тех пор, пока не получим пустую стопку.

Теперь, в вашем случае, непосредственно перед тем, как поместить узлы в стек, вам нужно проверить, активен или неактивен указанный узел (т. Е. дочерние элементы выскочившего узла). В этом случае вы не будете выполнять поиск вниз при достижении неактивного узла. Наконец, сообщайте только обо всех сгенерированных путях, что их конечный узел является листом (вы можете легко найти листья во время поиска, узел, у которого нет дочерних узлов).

Предположим, что

 A 1  /  /   B C -- G 2 3 -- 7  /    lt;=gt; /     D E F J 4 5 6 10  /   /    H I K 8 9 11  

Поэтому я могу предложить решение вашей проблемы, используя алгоритм глубинного первого поиска.

 /* A - 1, B - 2, C - 3, D - 4, E - 5, F - 6, G - 7, H - 8, I - 9, J - 10, K - 11. */ #include lt;iostreamgt; #include lt;vectorgt; #include lt;stringgt; #include lt;algorithmgt; using namespace std; const int maximumSize=20; int vertices, edges; vectorlt;intgt; visited0(maximumSize, 0); vectorlt;intgt; visited1(maximumSize, 0); vectorlt;intgt; graph[maximumSize]; vectorlt;intgt; distances(maximumSize, 0); vectorlt;stringgt; graphPaths; string path; vectorlt;intgt; green(maximumSize, 0); templatelt;class Typegt; void showContent1D(Typeamp; input) {  for(int i=0; ilt;input.size();   i)  {  coutlt;lt;input[i]lt;lt;", ";  }  return; } void showContentVectorString(vectorlt;stringgt;amp; input) {  for(int i=0; ilt;input.size();   i)  {  coutlt;lt;input[i]lt;lt;", ";  }  return; } void createGraph() {  cingt;gt;verticesgt;gt;edges;  int vertex0, vertex1;  for(int i=1; ilt;=edges;   i)  {  cingt;gt;vertex0gt;gt;vertex1;  graph[vertex0].push_back(vertex1);  graph[vertex1].push_back(vertex0);  }  for(int i=1; ilt;=vertices;   i)  {  cingt;gt;green[i];  }  return; } void dfs0(int current, int previous) {  if(visited0[current]==1)  {  return;  }  visited0[current]=1;  distances[current]=0;  for(int next : graph[current])  {  if(next==previous)  {  continue;  }  dfs0(next, current);  distances[current]=max(distances[current], distances[next] 1);  }  return; } void dfs1(int root, int current, int previous) {  if(visited1[current]==1)  {  return;  }  visited1[current]=1;  if(green[current]==1)  {  if(distances[current]!=0)  {  path.append(to_string(current));  path.append("-gt;");  }  else  {  path.append(to_string(current));  graphPaths.push_back(path);  path.pop_back();  }  }  for(int next : graph[current])  {  if(next==previous)  {  continue;  }  dfs1(root, next, current);  }  if(root==previous)  {  path.clear();  path.append(to_string(root));  path.append("-gt;");  }  return; } void solve() {  createGraph();  dfs0(1, 0);  dfs1(1, 1, 0);  coutlt;lt;"graphPaths: ";  showContentVectorString(graphPaths);  coutlt;lt;endl;  return; } int main() {  solve();  return 0; }  

Ввод:

 11 10 1 2 1 3 2 4 2 5 4 8 4 9 3 6 3 7 7 10 10 11 1 1 1 1 0 0 1 0 1 1 0  

Вот результат:

 graphPaths: 1-gt;2-gt;4-gt;9,