Matriz de Adjacências

Programação Java
,
#1

Boa tarde, eu tenho algumas duvidas acerca de matrizes de adjacências. Vou deixar em topicos para que seja mais fácil perceber.

  1. Como posso selecionar um vertice e descobrir os que estão adjacentes a esse mesmo vertice.
  2. Como posso pegar num vértice e seguir caminho até ao fim da ligação mutua que vá existindo entre cada vertice.

Por exemplo, tenho 2 utilizadores numa rede social, e tenho que saber o caminho mais curto entre esses dois, e em que passe pelas n cidades que cada utilizador tem como local de amigos.

Pensei num algoritmo de Dijkstra, mas não estou a idealizar como posso andar numa matriz de adjacencias e posteriormente pegar em cada cidade em que o utilizador tenha amigos pelo caminho.

Espero que tenha sido claro nas duvidas que tenho e agradeço a quem me possa ajudar.

Obrigado.

#2

Vamos lá.

  1. Implementar um grafo usando matriz de adjacências vai implicar em algumas coisas. a) não poderá haver mais de uma aresta entre dois vértices; b) o tratamento de laços, ou seja, uma aresta de um vértice a ele mesmo, tem que ser diferenciado. Essa característica é considerada como uma “anomalia” e normalmente não precisa ser representada dada a natureza do que você está representando com o grafo; c) caso seu grafo seja esparso, ou seja, a relação entre vértices e arestas seja baixa, vai haver desperdício de tempo para encontrar os vértices adjacentes, chegando aqui na sua pergunta. Em uma matriz de adjacências, cada coluna ou linha da matriz conterá a ligação entre dois vértices, sendo assim, basta iterar pela linha ou coluna do vértice desejado e ir verificando em quais vértices há ligação. Pela natureza do seu problema, você está implementando um grafo ponderado, então o que há na sua matriz é o peso entre dois vértices. É isso?

  2. Você quer o menor caminho, certo? O algoritmo base é o da busca em largura, que tem que ser “melhorado” para calcular os menores caminhos entre os vértices. Um algoritmo é o de Dijkstra que você comentou que resolve esse problema para arestas com valores positivos. Se precisar lidar com valores negativos, você terá que usar o algoritmo de Bellman-Ford.

Sinceramente, recomendo que primeiro você entenda o que é um grafo, quais suas características e propriedades. Estude como implementar, pois há várias maneiras, com prós e contras: lista de arestas, matriz de adjacências, lista de adjacências, chave-valor, encadeamento… Estude também os digrafos (lê-se di-grafos, sem tonicidade na primeira sílaba).

Depois disso, estude os algoritmos fundamentais: Busca em profundidade (Depth-first Search), Busca em largura (Breadth-first Search), Components Conexos (Connected Components) e algoritmos de extração de propriedades, como grau dos vértices, etc.

Então, depois de tudo isso, estude os algoritmos de menor caminho (Dijkstra) e os de árvores geradoras mínimas (minimum spanning trees) os principais são a) Prim-Jarnik; b) Kruskal e c) Boruvka.

Aí sim, sabendo como as coisas funcionam de verdade, instancie seu problema. De bate pronto não me parece que seu problema é polinomial, dado a essa característica de levar em consideração as cidades dos amigos… Provavelmente você precisará computar isso com alguma técnica de otimização.

Enfim, vc tem bastante coisa para fazer. Há bastante bibliografia. Eu recomendo, para começar, o livro Algorithms (https://algs4.cs.princeton.edu/home/). Para mim é um dos melhores, senão o melhor, livro sobre algoritmos e estruturas de dados essenciais.

1 curtida
#3

Sim, obrigado pela sua resposta.
No exercício que eu tenho que fazer foi-me pedido que carregasse os usuários através de uma matriz de adjacências. Já resolvi quase tudo que tinha que fazer, apenas continua a surgir-me o problema de como guardar os usuários e poder fazer uma relação de mutualidade entre todos. Sei que tenho que ver se a coluna é compativel com todas as linhas, ou seja, verificar se o usuário é amigo (Contenha o 1 na matriz [ user][ amigo ] ). Mas estou a ter um problema em como idealizar isto. Vou deixar o que tenho do exercicio até agora e se você me puder dizer o que estou a fazer mal agradecia.
Eu não sei se estou a ser correto a passar para uma list algo de uma matriz, mas pareceu-me ser mais fácil porque eu tenho que organizar qual usuário tem mais amigos e um compare pareceu mais prático.

/*2. Devolver os amigos comuns entre os n utilizadores mais populares da rede. A popularidade de um
    utilizador é dada pelo seu número de amizades.*/
public List<User> comuns (AdjacencyMatrixGraph<User,Relationship> friendshipGraph, int n){
    popularity = new ArrayList<User>();
    inNeighbors = new ArrayList<User>();
    int numero;
    for (User linha : friendshipGraph.vertices()) {
        numero = 0;
        for (Relationship coluna : friendshipGraph.edges()) {
            if (coluna.getUser2() != null) {
                numero++;
                friendshipGraph.toIndex(linha)
                linha.setAmigosUser(numero);
                popularity.remove(linha);
                popularity.add(linha);
            }
        }
    }
    popularity.sort(maisPopulares);
    for (int i = 0; i< n;i++){
        if(popularity.contains(u)){
            friendshipGraph.outgoingEdges(u);
            for
            }
        }

return comuns(friendshipGraph, n);
}



public static Comparator<User> maisPopulares = new Comparator<User>(){
    @Override
    public int compare(User u1, User u2) {
        int  cmp = Integer.compare(u2.getAmigosUser(), u1.getAmigosUser());
        return cmp;
    }

};

Com os primeiro for eu vou correr a matriz e contar os amigos de cada linha (usuário) e adicionar ao usuario a quantidade de amigos, e depois eu adiciono esse mesmo usuário a uma lista popularity. Depois nessa lista eu faço o sort por amigos.
Depois no segundo eu queria ver se em cada linha tinha o tal amigo, e faria isso para todas as linhas e se tivesse em todas guardava, mas não sei se isto é possivel.
Estou no caminho certo ou fiz algo de errado e o que teria que corrigir?

De novo, muito obrigado pela sua resposta, me ajudou imenso!