Como encontrar sub-árvores em árvores não binárias

5

Eu tenho uma árvore não-binária.
Eu quero encontrar todas as "sub-árvores" que estão conectadas ao root.

A subárvore é um grupo de links de nós de árvores.

cadagrupoécoloridoemsuaprópriacor.

Qualseriaamelhorabordagem?Executarrecursãoparabaixoeparacimaparacadanó?

Aestruturadedadosdecadatreenodeéumalistadefilhos,listadepais.(otipodefilhosepaissãotreenodes)

Esclarecimento:

Grupodefinidosehouverumtipode"fechamento" entre os nós em que a própria raiz não faz parte do fechamento.
Como você pode ver no gráfico, você não pode viajar de rosa para outros nós (você NÃO PODE usar root). Do nó marrom, você pode viajar para o seu filho, para que este seja outro grupo.

Finalmente, você pode viajar de qualquer nó ciano para outros nós cianos, para formar outro grupo

    
por kenny 10.01.2012 / 10:15
fonte

1 resposta

1

Você pode usar um algoritmo BFS (um algoritmo de gráfico explicado em Wikipedia ), começando pelo nó que você deseja para fazer root.

O algoritmo se comporta assim:

procedure BFS(G,v,btree):
      create a queue Q
      enqueue v onto Q
      mark v
      btree = new Tree(v);//Create a tree structure with v as root
      while Q is not empty:
          t ← Q.dequeue()
          btree.add(t) // Here its where you add elements to your tree
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

Quando Q está vazio significa que você processou todos os nós possíveis e todos eles foram adicionados à sua árvore binária (btree).

Depois de ter sua btree, você pode aplicar qualquer algoritmo simples para obter o que precisa

    
por 10.01.2012 / 15:27
fonte