Encontrar uma Árvore geradora Mínima a partir de uma Lista de Adjacência, onde a Lista de Adjacência é uma matriz de seqüência de caracteres usando o Algoritmo de Prims

StackOverflow https://stackoverflow.com/questions/9449967

Pergunta

Então eu preciso de alguma ajuda vinda acima com uma maneira de encontrar uma árvore geradora Mínima.Suponha que eu tenha meu gráfico na forma de uma lista de adjacência:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

A primeira letra diz qual o nó em que você está olhando, e o número indica quantas conexões para qualquer outro nó existem.Por exemplo, Um tem duas conexões: uma para cada um a B e I.Depois disso, o número que segue as letras de simplesmente dizer o peso de uma aresta.B tem peso de 12 e I tem peso 25.Então, eu tinha planejado originalmente para representar essa coisa toda como uma matriz de Seqüência de caracteres chamado Graph[8].Cada linha seria um slot diferente na matriz.Estou tendo dificuldades em descobrir como fazer isso com Prims ou Kruskalls algoritmo.

Foi útil?

Solução

Suponha que eu tenha a minha árvore sob a forma de uma lista de adjacência

É importante (para o seu entendimento) para a nota que tem uma conectado gráfico neste tipo de lista de adjacência, mas acho que foi apenas um erro de digitação.Vou propor isso como uma edição, mas eu só quero que você saiba.O fato de que ele é um gráfico e não de uma árvore pode ser visto a partir dessas linhas:

A 2 B 12 I 25
B 3 C 10 H 40 I 8

Aqui você tem um círculo já em A-B-I:

     A
  12/_\25
   B 8 I

Ter um círculo, por definição, significa que ela não pode ser uma árvore!Há mais uma coisa se pode ver do jeito que eu apresentei essa subgraph:as bordas têm pesos, não a nós.

Agora vamos dar uma olhada em seu fornecido exemplo: 

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

Primeiro de tudo, podemos ver que esta lista de adjacência é incorreto ou já otimizado para as suas necessidades.Isto pode, por exemplo, ser visto a partir das linhas de

E 2 F 60 G 38
F 0

A primeira linha mostra uma borda de E para F, mas a segunda linha diz F tinha um grau de 0, mas o grau é definido pelas arestas incidentes a ele!

É isso que a lista de adjacência de aparência se foi 'completo':

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35

Podemos ver muita redundância porque cada aresta ocorre duas vezes, por isso, o seu 'otimizado' lista de adjacência melhor se adapte às suas necessidades - seria este 'completo', um exemplo seria fazer muitas inútil verifica.No entanto, você deve apenas contar sobre isso, se você pode ter certeza de que todos os dados fornecidos para o seu código já está 'otimizado' (ou melhor, neste formato)!Vou tomar isso como um dado a partir de agora.

Vamos conversar sobre a sua estrutura de dados.Você pode, claro, usar de sua proposta de matriz de seqüências de caracteres, mas para ser honesto, eu prefiro recomendar algo como @AmirAfghani proposta de estrutura de dados.Usando sua abordagem para facilitar o seu trabalho (como ele é, como ele apontou-se - ia estar mais perto de sua representação mental) e ainda mais eficiente (eu acho, não contam com este adivinhar ;)) como você estaria fazendo muitos operações em cadeias de caracteres em contrário.No título você perguntou depois de Prim algoritmo, mas em seu real pergunta que você disse ou Prim ou de Kruskal-se.Eu irei com Kruskal simplesmente porque o seu algoritmo é a maneira mais fácil e você parece aceitar ambos.

De Kruskal algoritmo

De Kruskal algoritmo é bastante simples, é basicamente:

  • Começar com cada nó, mas sem bordas

Repita o seguinte sempre que possível:

  • A partir de todos os não utilizados/unchosen bordas escolher aquele com o menor peso (se houver mais de um:basta escolher um deles)
  • Verifique se esta vantagem poderia causar um círculo, se não, marque-a como escolhido e 'discard' - lo.
  • Se ele não causar um círculo, usá-lo e marcá-lo como usado e/ou escolhida.

Isso é tudo.É realmente muito simples.No entanto, gostaria de mencionar uma coisa neste ponto, eu acho ele melhor se encaixa aqui:não há "o mínimo spanning tree" em geral, mas "um mínimo de spanning tree" como pode haver muitas, portanto, seus resultados podem variar!

De volta à sua estrutura de dados!Agora você pode ver por que seria uma má ideia usar uma matriz de strings como uma estrutura de dados.Seria repita muitas operações em cadeias de caracteres (por exemplo, a verificar o peso de cada aresta) e strings são imutáveis, isso significa que você não pode simplesmente 'jogar fora' uma das extremidades ou marca a uma das bordas de qualquer maneira.Utilizando uma abordagem diferente, você pode apenas definir o peso de -1, ou mesmo remover a entrada para a borda!

Pesquisa De Profundidade-Primeiro

Pelo que tenho visto acho que o principal problema é decidir se uma borda poderia causar um círculo ou não, certo?Para decidir isso, provavelmente você vai ter que chamar uma Pesquisa de Profundidade-Primeiro algoritmo e usar o valor de retorno.A idéia básica é esta:iniciar a partir de um de nós (eu vou chamar esse nó raiz) e tentar encontrar um caminho para o nó na outra extremidade da borda (vou chamar a este nó, o nó de destino).(é claro que no gráfico que não tem essa borda ainda)

  • Escolha um unvisited aresta incidente a sua raiz
  • Marcar este escolhido de borda como visitado (ou algo assim, o que você quiser)
  • repita os dois últimos passos para o nó do outro lado da borda visitou
  • sempre que existem sem as bordas, voltar de uma borda
  • se você está de volta em sua raiz e não têm as arestas incidentes a ele, você está feito.retornar false.
  • se você, em qualquer ponto visite o seu nó de destino, você está feito.retornar true.

agora, se esse método retorna true esta vantagem poderia causar um círculo.

Outras dicas

Esta não é uma resposta direta à sua pergunta por dizer (parece que você está a fazer o dever de casa), mas eu acho que vai ajudar você a começar.Por que não criar uma estrutura de dados que mais se aproxima de seu modelo mental e construir a partir daí?

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top