• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Warrior

Grafos

30 mensagens neste tópico

Deixo aqui o material sobre grafos das edições da Revista PROGRAMAR 10 e 12.


Grafos – A resolução simples de muitos problemas complexos

Introdução: O que é um grafo

O leitor certamente que já ouviu falar em grafos. São amplamente usados em matemática, mas sobretudo em programação.

Formalmente, um grafo é uma colecção de vértices (V) e uma colecção de arcos (E) constituídos por pares de vértices. É uma estrutura usada para representar um modelo em que existem relações entre os objectos de uma certa colecção.

Pense nos vértices como "locais". O conjunto dos vértices é o conjunto de todos os locais possíveis. Nesta analogia, os arcos (ou arestas) representam caminhos entre estes locais. O conjunto E (vou usar o termo mais comum – "E" do inglês "edges") contém todas as ligações entre os locais.

Utilizar grafos é de grande utilidade na representação de problemas da vida real.

Podem ser cidades, e uma rede de estradas. Redes de computadores. Até mesmo os movimentos de um cavalo num tabuleiro de xadrez podem ser representados através de um grafo. Na prática:

  • As linhas de metro das grandes cidades utilizam grafos de modo a minimizarem o tempo das ligações;
  • A distribuição de correio, minimizando percursos de forma a optimizar as deslocações, tanto para um único carteiro como para uma equipa (o mesmo se aplica a empresas de distribuição);
  • Os sistemas de patrulha da PSP permitem estudos de optimização recorrendo a grafos.

E depois de representá-los correctamente, o que podemos descobrir? O caminho mais curto entre duas cidades num mapa; dadas as coordenadas de n cidades, que estradas construir de modo que o número de quilómetros de estrada seja mínimo mas fiquem todas conectadas; dado um mapa de uma casa (em que paredes e chão são representados com caracteres diferentes) saber qual a divisão com maior área; etc.

As possibilidades são grandes, e ficarão admirados com a facilidade com que estes problemas são resolvidos.

Representação

Graficamente, um grafo é normalmente representado da seguinte forma:

Grafo: exemplo 1

Grafo: exemplo 2

Vértices são pontos ou círculos; arcos são linhas entre eles.

Usando o primeiro exemplo, V = {1, 2, 3, 4, 5, 6} e E = {(1,3), (1,6), (2,5), (3,4), (3,6)}.

Cada vértice (também chamado "") é um membro do conjunto V. Cada arco é um membro do conjunto E.

Terminologia

Como é de esperar, tendo aplicações tão variadas, o grafo adapta-se às nossas necessidades. Assim, existem vários tipos de grafos. Aliados a isso, existem termos comummente usados para descrever um grafo, ou parte dele. Vou listar alguns (entre eles os mais comuns):

Vértice isolado
Um vértice é considerado isolado se não possuir nenhuma ligação a outro vértice (bastante óbvio).
Grafo trivial (ou ponto)
Grafo sem arestas e um único nó.
Laço (ou loop/self-loop)
Um arco é um laço se em ambas as extremidades estiver o mesmo vértice (nenhum dos grafos apresentados possui laços).
Grafo simples
Um grafo é simples se não contiver laços nem arcos repetidos em E.
Vértices adjacentes
Dois vértices (u e v) são adjacentes se existir um arco que possui uma extremidade em u e outra em v. Os vizinhos de um vértice são todos os vértices adjacentes a ele.
Grafo pesado (ou grafo de arcos pesados)
A cada aresta está associado um valor. Pode ser uma distância, um custo, seja o que for.

Uma definição similar existe para grafo de nós pesados.

Grau de um vértice(ou valência)
O grau de um vértice é o número de arcos que lhe são incidentes. Um arco (u,v) é incidente tanto no vértice u como no vértice v.

Pode-se distinguir grau de entrada e grau de saída em grafos direccionados (ver à frente).

Grafo direccionado
Cada arco tem um nó de origem e um nó de chegada. O exemplo típico é o das redes de estradas, uma vez que existem estradas só com um sentido seria o caos se um GPS não soubesse distingui-las.

Para os representar, são desenhados com setas para representar a direcção:

Grafo: exemplo 3 (direccionado)

Da teoria para a prática

Certamente que tudo o que foi demonstrado até agora é muito bonito, mas o que interessa ao leitor é saber como transformar aqueles desenhos e aquelas setas em algo que o seu programa possa interpretar.

Existem diversas formas de os armazenar, umas que ocupam mais espaço em memória mas mais eficientes, outras que ocupam menos espaço, são mais eficientes mas mais difíceis de programar. Vou somente falar das mais habituais.

Matriz de adjacência

Esta é uma representação bastante fácil de programar, mas bastante pouco eficiente em termos de memória.

Consiste uma matriz N x N (onde N é um número de vértices) onde (i,j) indica se existe uma ligação do vértice i para o vértice j. Alternativamente, pode representar o tamanho dessa ligação.

Vantagens:

  • Fácil de programar.
  • Pode representar um grafo pesado sem comprometer a complexidade.
  • Caso o grafo não seja pesado e seja possível existir mais do que uma ligação entre dois vértices, (i,j) pode representar o número de ligações entre eles.
  • Verificar se dois vértices são adjacentes é muito rápido, tal como adicionar ou remover ligações.

Desvantagens:

  • Elevado desperdício de memória (especialmente se o grafo for disperso).
  • Debugging é difícil, uma vez que a matriz tende a ser grande.
  • Listar todas as arestas incidentes num dado vértice é demorado (força-nos a percorrer todos os vértices).

Como exemplo, o primeiro grafo apresentado teria este aspecto:

  V1 V2 V3 V4 V5 V6
V1 0 0 1 0 0 1
V2 0 0 0 0 1 0
V3 1 0 0 1 0 1
V4 0 0 1 0 0 0
V5 0 1 0 0 0 0
V6 1 0 1 0 0 0

Listas de adjacência

Nesta representação limitamos-nos a guardar a informação de todas as arestas incidentes num dado vértice.

Isto pode ser feito usando um vector de tamanho V (número de vértices), onde v[ i ] guardará a lista dos arcos ou vértices conectados ao vértice i.

A maneira de guardar estes vértices/arcos varia, dependendo da linguagem, podendo-se usar listas encadeadas ou mesmo transformar o vector numa matriz.

Vantagens:

  • Listar todas as arestas incidentes num dado vértice é fácil (a operação mais frequente na maioria dos algoritmos).
  • Baixo desperdício de memória.

Desvantagens:

  • Dependendo da implementação, difícil de programar.
  • Representar um grafo pesado implica uma matriz de estruturas ou mais um campo na lista encadeada.
  • Para verificar se dois vértices são adjacentes necessitamos de percorrer todos os vértices adjacentes a um deles.

Mais uma vez, o primeiro grafo fornecido poderia ser representado desta forma:

Vértice Vértices Adjacentes
1 3, 6
2 5
3 1, 4, 6
4 3
5 2
6 1, 3

Resolvendo problemas – Algoritmos comuns

Flood Fill

Geralmente estes problemas são muito simples de perceber, e mais ainda de implementar.

Vejamos um exemplo:

Num país distante, um terramoto destruiu uma grande parte das estradas que ligavam as suas cidades. Assim, certas zonas ficaram sem qualquer meio de contactar com outras. O nosso objectivo é saber quantas destas zonas é que existem. Uma zona é definida como sendo uma ou mais cidades, sem qualquer ligação ao exterior.

Sem grandes esforços, podemos chegar a um algoritmo simples:

  • Precisamos de um vector que nos diga, num dado instante, se o elemento i foi ou não visitado (inicialmente todos os elementos começam a 0 (não visitado).
  • Começando no primeiro elemento, marcar todos os elementos que lhe estão ligados como visitados. E todos os que estão ligados a esses (que ainda não foram marcados, obviamente) também. E por aí fora.
  • Se quando chegarmos ao fim ainda houver elementos por marcar, então estamos perante a existência um novo centro urbano.

Um flood fill pode ser feito basicamente de 2 maneiras: em profundidade (DFS – depth-first search) ou em largura (BFS – breadth-first search) (simplificando, pois existem mais alternativas como o "DFS with iterative deepening" ou "breadth-first scanning").

Breadth-first search

Podemos ver a pesquisa em largura como uma torneira aberta num chão de tijoleira: a primeira a ser molhada é a que se encontra no local onde está a torneira. Todas as que estão à volta serão as próximas, e por aí em diante, numa expansão a partir de um dado centro.

Este algoritmo normalmente não levanta muitos problemas a implementar, quer iterativa quer recursivamente: temos o nosso vector de elementos visitados (e por visitar) e uma lista dos elementos que acabaram de ser visitados (recentemente). Para cada um destes últimos, adicionamos a uma nova lista os seus vizinhos ainda não visitados. Depois de termos feito isto com todos os elementos, passamos para a nova lista (e podemos esquecer a antiga).

Depth-first search

Os algoritmos de pesquisa em profundidade normalmente são mais complicados de compreender, porque dão trabalho a implementar iterativamente e muita gente não está familiarizada com a recursividade. Contudo, após esse problema estar ultrapassado, é ainda mais fácil de implementar do que o BFS.

Vamos ver o DFS como um rato à procura de um queijo perdido num labirinto: ele escolhe um caminho, e mal encontra um beco sem saída volta para trás e vira pelo primeiro caminho ainda não pesquisado. É exactamente este funcionamento que vamos implementar, desta vez em pseudo-código.

Partindo do vértice inicial, v.

função dfs(v)
  marcar v como visitado
  para todos os vértices i adjacentes a v
    se i não tiver sido visitado
      dfs(i)

Problemas modelo

Street Race (International Olympiads in Informatics 95)

Dados: um grafo direccionado, um ponto inicial e um ponto final.

Encontrar todos os pontos p que um caminho do ponto inicial para o ponto final deve atravessar obrigatoriamente.

Análise: O algoritmo mais simples é remover cada ponto e verificar se o ponto final ainda é alcançado a partir do ponto inicial.

Fazendo um Flood Fill no ponto de partida, verificamos se o ponto de chegada foi ou não marcado como visitado (repetimos este procedimento removendo sempre um ponto de cada vez).

The Castle (International Olympiads in Informatics 94)

Dados: um mapa de um castelo (uma matriz) onde # representa uma parede e . uma casa em branco.

Descobrir qual o tamanho da maior sala do castelo, após deitar abaixo uma das paredes.

Análise: Ao ser fornecida a matriz temos uma representação implícita do grafo, cada casa sendo um vértice. Não precisamos de a transformar numa matriz/lista de adjacência, podemos usá-la para saber quais os vértices adjacentes.

Mais uma vez, deitamos uma parede abaixo e verificamos o tamanho da maior sala (através de um Flood Fill e contando quantos quadrados foram visitados).

Fontes

  1. Wikipedia: https://en.wikipedia.org/
  2. USACO Training Program: http://train.usaco.org
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Shortest Path (o caminho mais curto)

Este é certamente um dos problemas mais simples de enunciar.

Por exemplo:

Dado um conjunto de cidades, ligadas por estradas, e o respectivo comprimento de cada uma, calcular a distância mínima a ser percorrida entre duas dadas cidades.

Podemos modelar isto com recurso a um grafo pesado, é demais evidente. Cada cidade representa um nó e cada estrada que liga dois nós representa um arco.

Primeiro de tudo, é importante reparar: o facto de existir uma estrada “directa” entre a cidade A e a cidade B, não significa que o caminho mais curto entre as duas cidades seja essa estrada. Pode existir uma cidade C, intermédia, cujo caminho mais curto passe por ela.

Vamos então ver os principais algoritmos.

Algoritmo de Dijkstra

Descrição

O algoritmo de Dijkstra é muito provavelmente o algoritmo mais conhecido no tratamento de grafos.

Este algoritmo não encontra só o caminho mais curto entre duas cidades, mas sim o caminho mais curto entre uma cidade (chamada origem) e todas as outras.

Parte da seguinte importante e simples propriedade: se de todos os arcos que saem do nó A, o arco A-B é o mais curto, então a ligação mais curta entre estes dois nós é através desse arco. Bastante óbvio, uma vez que qualquer outro caminho usando um outro arco seria obrigatoriamente maior, partindo do princípio que todos os arcos têm um peso positivo, claro.

Pseudo-código

# distancia(j) distância do nó de origem ao nó j
# pai(j) nó anterior ao j, do caminho mais curto (para podermos reconstruir o caminho) 

Para todos os nós i
    distancia(i) = infinito  # não alcancável
    visitado(i) = Falso
    pai(i) = nil      # ainda nenhum caminho até ao nó

distancia(origem) = 0 # origem -> a origem do percurso

enquanto(nos_visitados < tamanho_do_grafo)
    # encontrar o vértice não visitado com a distância mínima à origem; chamemos-lhe i
    assert (distancia(i) != infinito, "Grafo não é conexo") 

    visitado(i) = Verdadeiro # marcamos o vértice i como visitado 

    # actualizamos as distância para todos os vizinhos de i
    Para todos os vizinhos j do vértice i
        se distancia(i) + peso(i,j) < distancia(j) então
            distancia(j) = distancia(i) + peso(i,j)
            pai(j) = i

Análise de complexidade

Compreender esta secção implica ter conhecimentos de análise de complexidade que não vou explicar neste artigo.

Como podem ter constatado, o pseudo-código está “incompleto” por não explicar como encontrar o vértice não visitado de distância mínima.

Foi propositado por existirem duas possibilidades:

  • uma pesquisa linear, percorrendo todos os vértices (a mais normal), originando numa complexidade O(V2);
  • utilizar uma heap para encontrar o mínimo, tendo uma complexidade O(V log E), significativamente mais rápido se o grafo for esparso (tiver uma relação arcos/vértices baixa).

Extensões

  • Grafos direccionados não são um problema para este algoritmo.
  • Como é possível concluir partindo da descrição, grafos com arcos com pesos negativos produzem respostas incorrectas, de modo que este algoritmo não pode ser usado nessa situação, devendo-se recorrer ao algoritmo de Bellman-Ford.
  • Apesar de mais rápido (principalmente se utilizarmos uma heap), encontrar o caminho mais curto entre todos os vértices é mais simples recorrendo ao algoritmo de Floyd-Warshall.

Problemas Modelo

Movimentos a cavalo (Knight Moves)

Problema: Dadas duas posições num tabuleiro de xadrez, determinar o número mínimo de movimentos que um cavalo deve fazer para chegar de uma casa à outra.

Análise: O tabuleiro pode ser modelado como um grafo, sabendo que existe ligação entre duas casas se um cavalo se puder deslocar entre elas (e não se forem adjacentes, como acontece por exemplo num flood-fill BFS).

Repare-se que dada uma posição sabemos imediatamente para quais se pode deslocar o cavalo, de modo que não precisamos de o representar em memória do modo “clássico”, mas usar uma representação implícita.

Percursos do caminho de ferro (Railroad Routing - USACO Training Camp 1997, Contest 1 - simplificado)

Problema: É nos dado um mapa (matriz) onde m[ i ][ j ] representa uma dada elevação nesse quilómetro quadrado. Pretendemos construir um caminho de ferro que conecte 2 pontos.

O custo normal por quilómetro é de 100€. Carris que necessitem de ganhar ou perder elevação entre quadrículas, são cobrados 100€ + 3x variação_na_elevação. Uma mudança de direcção de 90º dentro de uma quadrícula implica um custo de 40€.

Qual o custo mínimo para construir o percurso?

Análise: Este é um problema standard de shortest path.

Contudo, em vez de criarmos um nó por quadrícula, devemos criar 4, representando as 4 possíveis direcções de entrar numa dada quadrícula.

Agora podemos criar as ligações correspondentes, e resolvê-lo.

Algoritmo de Floyd-Warshall

Descrição

E se em vez do caminho mais curto entre duas cidades, pretendemos construir uma matriz de adjacência m onde m[ i ][ j ] representa o caminho mais curto da cidade i à cidade j?

Nesse caso, esta é a solução mais simples.

A ideia é a seguinte: pegando num outro vértice K, caso a distância m[ i] [ j]  seja maior do que a distância m[ i ][ k ]+m[ k ][ j], podemos afirmar que encontrámos um novo caminho melhor que o anterior, e portanto podemos actualizar m[ i ][ j ].

Provar que esta formulação produz a resposta óptima já é mais complicado, e não vai ser abordado.

Pseudo-código

# dist(i,j) é a "melhor" distância até agora do vértice i ao vértice j

# Comecemos com todas as ligações passando por um único caminho

Para i = 1 até n fazer
    Para j = 1 até n fazer
        dist(i,j) = peso(i,j) 

Para k = 1 até n fazer # k é o vértice "intermédio"
    Para i = 1 até n fazer
        Para j = 1 até n fazer
            se (dist(i,k) + dist(k,j) < dist(i,j)) então # caminho mais curto
                dist(i,j) = dist(i,k) + dist(k,j)

Análise de complexidade

Este algoritmo é claramente O(V3), muito provavelmente o algoritmo com análise mais simples que existe.

Extensões

  • Para este algoritmo pesos negativos não são tão devastadores como para o algoritmo de Dijkstra.
    Desde que não existam ciclos negativos, o algoritmo funciona como pretendemos. (Caso exista um ciclo negativo ele pode ser percorrido tantas vezes quantas quisermos para ter sempre caminhos mais curtos.)

Problemas Modelo

Diâmetro de um grafo

Problema: Dado um grafo conexo, não direccionado e pesado, encontrar os dois vértices que estão mais afastados.

Análise: Calcula-se o caminho mais curto entre todos os vértices e acha-se o máximo da matriz.

Minimal Spanning Tree (árvore de extensão mínima)

Numa Minimal Spanning Tree nós procuramos o conjunto mínimo de arcos necessários para conectar todos os nós.

Suponham que trabalham numa companhia que gere uma rede de auto-estradas. Recentemente, saiu uma lei que obriga a que os camionistas percorram os seus trajectos em estradas iluminadas com postes de 10m.

Como os vossos postes só têm 7m, estão numa boa alhada.

Pretendem então substituir os postes em algumas das vossas auto-estradas, aquelas necessárias para que todas as cidades possam ser abastecidas convenientemente. Qual a distância mínima de autoestrada em que terão que substituir os postes?

Existem dois algoritmos muito usados na procura da árvore de extensão mínima, neste artigo decidi não abordar o algoritmo de Kruskal.

Algoritmo de Prim

Descrição

As semelhanças entre o algoritmo de Prim e o algoritmo de Dijkstra são tantas que eu quando os aprendi facilmente os trocava.

Para tal não acontecer, efectuava sempre o seguinte raciocínio, que no fundo é a sua explicação:

  • Suponhamos que tenho todos os nós conectados, excepto um.
  • Saber qual o arco a usar de modo a conectar este nó aos restantes é fácil – posso escolher o de tamanho menor.
  • Vamos então partir de um ponto. Este ponto vai ficar unido ao resto da árvore através da ligação ao arco mais próximo. Temos agora dois pontos.
  • Qual o próximo ponto a unir? Fácil. O ponto mais próximo dos dois que ainda não foi unido.

Esta metodologia obviamente nos leva à solução óptima (e por ser tão simples preferi explicá-la ao algoritmo de Kruskal).

Pseudo-código

# dist(j) é a distância do nó j à árvore
# pai(j) representa o nó até agora conectado à MST mais próximo do nó J
Para todos os nós i
    dist(i) = infinito  # sem ligações
    intree(i) = Falso   # sem nós na árvore
    pai(i) = nil 

tamanho_da_árvore = 1   # adicionar um nó à árvore
custo_da_árvore = 0                   
intree(1) = Verdadeiro
Para todos os vizinhos j do nó i   # actualizar as distâncias
    dist(j) = peso(1,j)
    pai(j) = 1 

enquanto (tamanho_da_árvore < tamanho_do_grafo)
    # encontrar o nó com a menor distância à árvore; chamar-lhe nó i 
    # obviamente um nó que não esteja "intree"
    assert (distance(i) != infinity, "Grafo não conexo") 

    # adicionar arco pai(i),i à MST
    tamanho_da_árvore = tamanho_da_árvore + 1
    custo_da_árvore = custo_da_árvore + dist(i)
    intree(i) = Verdadeiro     # marcar o nó i como estando na árvore 

# actualizar todas as distâncias depois do nó i ter sido adicionado
para todos os vizinhos j de i
    se (dist(j) > peso(i,j))
        dist(j) = peso(i,j)
        pai(j) = i

Análise de complexidade

Tal como para o algoritmo de Dijkstra, tempo de execução O(V2).

Podemos obter O(V log E) se recorrermos a uma heap.

Extensões

  • Funciona bem com grafos não pesados.
  • Não há problema com múltiplos arcos entre dois nós (ignoramos todos menos o menor, obviamente).
  • Se sofrer outras restrições (como 2 nós não poderem estar mais afastados do que X) então fica muito difícil de alterar.
  • Não funciona com grafos direccionados (em que pretendemos que sejam fortemente conexos – seja possível aceder de um vértice a todos os outros).

Problemas modelo

Highway Building (construindo uma autoestrada)

Problema: Pretende-se construir uma rede de auto-estradas que ligue as K maiores cidades de um país.

Sendo um país pobre, eles pretendem reduzir ao máximo o custo da obra. Sabendo que o custo de uma autoestrada é proporcional ao seu comprimento, e dadas as coordenadas das cidades, quais as cidades que devemos ligar para formar a requerida via rápida? (Nota: não se podem usar outros pontos como nós.)

Análise: Um problema simples de MST, usamos as cidades como nós e consideramos todas as ligações possíveis como arcos.

Referências

  1. USACO Training Pages: http://train.usaco.org
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já tive algum contacto com grafos, mas este teu artigo está espectacular.

Muito directo, muito simples (fácil de perceber para qualquer pessoa). Muito bom.

Cumprimentos~.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu tive a ler sobre os grafos e sobre o caminho mais curto, problema é que eu  sou fraco a programação e nao sei como posso passar de psuedo-codigo para codigo em c sharp, alguem me podia ajudar?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não há muito mais a fazer além de dar o código.

Tens dúvidas em que parte em particular?

É só criar os vectores "visitado", "distancia" e "pai", e depois escrever o código. Os ciclos "para" são fors, etc. E depende de como tens o vector armazenado em memória, o início do artigo fala sobre isso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tinha o texto sobre eulerian tours +- escrito, só que o tempo apertou e puff.

Depois sim, fluxo seria o próximo passo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas!

Estou a fazer um projecto que involve um grafo (neste caso cidades), e não estou a perceber muito bem como implementar a lista de adjacências. Matrizes e vectores estão fora de questão penso eu, uma vez que tem de ser possivel inserir até 10 000 cidades.

A minha dúvida é: em cada cidade definida por uma estrutura própria, devo ter um campo com um apontador para outra cidade (tipo) ou para um vertice genérico, com o custo e um apontador para um vertice seguinte? (Ou seja uma lista ligada "normal")...

Penso que me fiz entender. .  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nesse caso o ideal são listas de adjacência. Cada cidade tem uma lista de adjacências com as cidades vizinhas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Uma lista de adjacências implementada com "vectors" dinâmicos ocupa pouco espaço (pouco mais do que com listas) e é mais fácil de implementar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vou fazer aqui uma pequena pergunta:

Como exemplo, o primeiro gráfica apresentado teria este aspecto:

      V1  V2  V3  V4  V5  V6

V1 0 0 1 0 0 1

V2 0 0 0 0 1 0

V3 1 0 0 1 0 1

V4 0 0 1 0 0 0

V5 0 1 0 0 0 0

V6 1 0 1 0 0 0

Se o grafo fosse direccionado (vou tomar como exemplo aquele grafo direccionado dado) as ligações entre V1 e V3 deixariam de existir, ou seja, o valor na posição (V1,V3) seria 0, correcto?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

No primeiro problema apresentado na parte do Flood Fill não podia ser resolvido criando uma lista de adjacência e depois não bastava verificar quais os vértices que não tinham vértices adjacentes? Ou até podiamos implementar uma matriz de adjacência e fazer exactamente a mesma coisa (para cada linha da matriz verificar se nessa linha todos os elementos estão a 0)...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

No primeiro problema apresentado na parte do Flood Fill não podia ser resolvido criando uma lista de adjacência e depois não bastava verificar quais os vértices que não tinham vértices adjacentes? Ou até podiamos implementar uma matriz de adjacência e fazer exactamente a mesma coisa (para cada linha da matriz verificar se nessa linha todos os elementos estão a 0)...

Nop. Tu queres determinar grupos de cidades que estão isolados (i.e. que estão ligados entre si mas isolados dos outros).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que já entendi a ideia do Flood Fill.

Vou-me basear em dfs.

Basicamente, começamos com um vértice qualquer do grafo, geralmente pelo index 1 ou 0, depois para cada vértice adjacente a este marcámos como visitados e aprofundámos a nossa "pesquisa" sobre os mesmos, quando não restarem mais filhos do primeiro vamos para outro vértice, não marcado, com um novo componente.

É isto? 

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estou aqui com uma dúvida em MST, que é basicamente a formulação do algoritmo de Kruskal.

Penso que seria algo como isto.

enquanto existirem nós não visitados:
  # escolher edge E com menor peso e em que o vértice destino dessa edge
  # ainda não foi visitado para evitar ciclos
  pesoTotal = pesoTotal + pesoEdge
  marcar_edge(E)
return pesoTotal

Era algo como isto?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estou aqui com uma dúvida em MST, que é basicamente a formulação do algoritmo de Kruskal.

Penso que seria algo como isto.

enquanto existirem nós não visitados:
  # escolher edge E com menor peso e em que o vértice destino dessa edge
  # ainda não foi visitado para evitar ciclos
  pesoTotal = pesoTotal + pesoEdge
  marcar_edge(E)
return pesoTotal

Era algo como isto?

Pelo que percebi do Krustal, n exactamente.

Estás a percorrer os nós, o algoritmo de Krustal percorre as edges, da menor à maior.

Basicamente, ordenas uma lista com as edges, e vais retirando sempre a edge menor, verificando e adicionas essa edge apenas caso ela ligue duas árvores que não tenham sido ligadas anteriormente (a descrição que li, é caso a edge ligue duas árvores, adicioná-la ao grafo, e transformar esse par de árvores numa só, mas acho que vai dar ao mesmo, certo?).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Exactamente como o cynary disse, adicionas o edge se os vértices que ele liga estiverem em conjuntos diferentes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sei que já venho um pouquito atrasado, mas tenho de felicitar os autores deste post está muito bom!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas.

Tenho uma dúvida relativa ao algoritmo de dijkstra.

No exercicio da imagem abaixo como é que, do vértica A, seguindo o algoritmo, é escolhido o vértice B e não o C?

Eu sei que escolhendo o B é o caminho mais curto mas não é isso que o algoritmo me diz.

Alguém me pode ajudar?

gafob.th.jpg

Uploaded with ImageShack.us

Cumprimentos

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O "não é isso que o algoritmo me diz" significa o quê? Implementaste e não te dá esse caminho ou estás a resolver isto à mão?

O importante é que seguindo por B, chegas a E com peso 9, enquanto que seguindo por A chegas a E com peso 10. Assim, o predecessor do E é o B e não o C.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu estou a resolver à mão.

Sim eu sei, eu faço o caminho A, D, G. F, E mas do E como é que selecciono o C e não o B? já que, nessa etapa o B tem menor custo?

Não percebi muito bem a tua explicação... O predecessor do E nunca poderia ser o B nem o C dado que o grafo é dirigido e não existem os arcos que ligam B a E nem C a E.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Deves estar a ver um grafo diferente daquele que linkaste aqui (exercício IV.d). Existem edges B->E com custo 1 e C->E com custo 3

O caminho é G -> A -> B -> E -> H -> F -> D com custo total 14

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora