1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

[JAVA] contar numero de edges num treemap graph

Discussão em 'Programação' iniciada por Canhola, 16 de Dezembro de 2012. (Respostas: 2; Visualizações: 676)

  1. boas,

    é assim, não estou a conseguir implementar o metodo int edge( ), que consiste em retornar o número de arestas num grafo dirigido.
    O graph contém nós e arestas.

    Saber o numero de nós é facil:
    public int nodes()
    {
    return map.size();
    }

    Mas para saber o numero de arestas é mais complicado.

    Esta é a classe do graph:

    public class SMGraph<N extends Comparable<? super N>> implements Graph<N>
    {

    private TreeMap<N,TreeSet<N>> map;

    /**
    * Constructor.
    */
    public SMGraph()
    {
    map = new TreeMap<N, TreeSet<N> ( ) );
    }

    public int edges()
    {



    }

    Obrigado desde já!
     
  2. diogo_miguel

    diogo_miguel Power Member

    não tens de percorrer o grafo e ver como os nós estão ligados?
     
  3. mauro1855

    mauro1855 I'm cool cuz I Fold

    Não percebo absolutamente nada de Java.
    Dito isto, já trabalhei com Grafos e Árvores em C.

    Acho que também passa por perceber como é que a árvore está implementada.
    Uma hipótese que existe em C é com o conceito de ponteiro (que não sei se existe em Java) onde cada nó é uma estrutura de dados que contém um ponteiro que aponta para outro nó. Neste caso, uma forma de verificar o número total de arestas é fazeres um algoritmo DFS ou BFS com uma matriz/lista de "arestas visitadas" (sempre que queres avançar para o nó seguinte, verificas se a aresta pelo qual vais avançar já foi ou não visitada - caso ´não tenha sido visitada avanças, poens essa aresta como visitada e incrementas um contador; caso já tenha sido visitada, não avanças).
    Mas como digo, isto é um conceito que não sei se existe em Java.

    Outra forma de implementar grafos em C é com o que se chama uma matriz ou lista de adjacências. O primeiro índice da matriz indica o nó origem e o segundo índice da matriz indica o destino. Se nessa posição matriz[j] existir um número N, significa que existe uma aresta do nó i para o nó j com custo N. Neste caso bastaria simplesmente contar a quantidade de números existentes na matriz...
     

Partilhar esta Página