Ir para o conteúdo

Pesquisar na Comunidade

A mostrar resultados para tags ''grafos''.



Mais opções de pesquisa

  • Pesquisa por Tags

    Introduza as tags separadas por vírgulas.
  • Pesquisar por Autor

Tipo de Conteúdo


Fórum

  • Bem-vindos ao Portugal-a-Programar
    • Sugestões, Críticas ou Dúvidas relativas ao P@P
    • Acerca do P@P
    • Apresentações
  • Comunidade a Trabalhar
    • Wiki P@P
    • Apresentação de Projectos de Programação
    • Downloads
  • Revista PROGRAMAR
    • Revista PROGRAMAR
  • Desenvolvimento Geral
    • C
    • C++
    • Java
    • Haskell
    • Pascal
    • Python
    • Bases de Dados
    • Visual Basic Clássico
    • Visual Basic for Applications (VBA)
    • Dispositivos Móveis
    • Outras Linguagens
  • Desenvolvimento Orientado para Web
    • PHP
    • HTML
    • CSS
    • Javascript
    • Outras Linguagens de WebDevelopment
    • Desenvolvimento Web
  • Desenvolvimento .NET
    • C#
    • Visual Basic .NET
    • ASP.NET
    • WPF & SilverLight
  • Software e Sistemas Operativos
    • Software de Produtividade
    • Sistemas Operativos
    • SharePoint
    • Apresentação de Software
  • Informática Extra-Programação
    • Interfaces Visuais
    • Computação Gráfica
    • Algoritmia e Lógica
    • Segurança e Redes
    • Hardware
    • Electrónica
    • Automação Industrial
    • Dúvidas e Discussão de Programação
    • Notícias de Tecnologia
  • Outras Áreas
    • Matemática
    • Dúvidas Gerais
    • Discussão Geral
    • Eventos
    • Anúncios de Emprego
    • Tutoriais
    • Snippets / Armazém de Código
  • Arquivo Morto
    • Projectos Descontinuados
    • System Empires

Blogs

  • Blog dos Moderadores
  • Eventos
  • Notícias de Tecnologia
  • Blog do Staff
  • Revista PROGRAMAR
  • Projectos
  • Wiki

Categorias

  • Revista PROGRAMAR
  • Tutoriais
  • Textos Académicos
  • Exercícios Académicos
    • Exercícios c/ Solução
    • Exercícios s/ Solução
  • Bibliotecas e Aplicações
  • Outros



Filtrar por número de...

7 resultados

  1. [Resolvido] Travessias BFS e DFS

    Boas pessoal Alguém me consegue explicar qual seria o resultado da travessia BFS e DFS deste grafo: Ponto de partida por exemplo o A qual seria o resultado? Estive a ver alguns exemplo das travessias BFS e DFS mas quase todos são de árvores e sem direçoes, se alguem me poder ajudar agradecia. Cumps
  2. [Resolvido] Fazer Adjacencia em Grafo em PROLOG

    Olá não tenho nenhuma experiência em prolog, e sei que este forum é de perl, contudo acredito que alguém aqui possa me ajudar. tenho o seguinte código em prolog, e está dando erro. aresta (a,b). aresta (a,c). aresta (b,d). aresta (d,c). adjacente (N, F) :- aresta (N, F). adjacente (N, F) :- aresta (F, N). está dando o seguinte erro, ?- ['Grafo.pl']. ERROR: /home/crislanio/Área de Trabalho/Grafo.pl:1:7: Syntax error: Operator expected true. Att,
  3. [Resolvido] Ajuda compreensão codigo c++

    Boa noite comunidade Portugal-a-Programar, Gostaria de obter alguma ajuda na compreensão de um projecto de C++. Relativamente ao projecto, tenho que saber explicar: Para que serve a classe graphStl Para que serve a classe graphStlPath Para que serve a classe graphEdge Para que serve a classe graphVertex Saber explicar como foram construidos os seguintes 4 metodos que constituem o trabalho em questão: (foram usadas matrizes e etc...) Construir o grafo Apresentar todos os percursos entre dois possiveis depositos. apresentar o percurso entre dois depositos do mesmo tipo (fresco/normal) Calcular o percurso mais curto entre dois depositos. Se correrem o projecto irão perceber melhor o que este projecto faz Gostaria que alguem que consiga interpretar bem este projecto me saiba ajudar como isto funciona, no fundo é como se tivesse a comentar o codigo, é disso que necessito. Agradeço desde ja a ajuda. Aqui deixo o projecto em questão: https://www.dropbox.com/s/nso1az7m15gqic5/AIS_1130127.rar?dl=0
  4. Neo4j base de dados por grafos

    Estou a experimentar este novo sistema http://www.neo4j.org/, e fiquei fascinado, não tinha noção que este projecto estava tão avançado. Uma forma diferente de ver uma base de dados e com imensas aplicações práticas. Efetuar queries com Cypher é simplesmente intuitivo e poderoso. Adicionando a framework http://projects.spring.io/spring-data-neo4j/ é a cereja em cima do bolo. Encontrei também este refcard http://docs.neo4j.org/refcard/2.0/ E o server é fantástico, vejam uns videos aqui http://www.neo4j.org/tracks/neo4j_server
  5. Java- Construir Grafo

    Boas, tenho que fazer uma aplicação em Java que utiliza um grafo. Basicamente tenho que fazer uma cidade utilizando um grafo. A minha representação do grafo é uma lista de adjacências do tipo ArrayList<LinkedList<Ligacao>>. A Ligacao é a classe que contem o índice do nó a distancia e o peso (neste caso o valor da portagem). Os nós são o cruzamento entre as ruas e as avenidas, porque o grafo tem de ser como uma matriz, ou seja, o 1º nó só tem 2 ligações (direita e pra baixo), o último da 1ª linha só tem pra esquerda e pra baixo, o último da 1ª coluna só tem pra cima e pra direita e o último da última coluna tem pra cima e para a esquerda. A minha dúvida é como eu faço no construtor para criar as ligações entre os nós automaticamente? int avenidas; int ruas; public boolean[] visit; // array para marcar vertices visitados public int[] comp; // array para armazenas os caminhos mais curtos public LinkedList<Ligacao> auxList; // arrayList de lista ligada auxiliar public ArrayList<LinkedList<Ligacao>> listaAdjacencias; // arrayList de lista ligada para representar as adjacencias Queue queue = new LinkedList(); public Grafo() { //construtor por defeito } public Grafo(int avenidas, int ruas) { //construtor do Grafo this.avenidas = avenidas; this.ruas = ruas; int nVertices = avenidas * ruas; visit = new boolean[nVertices]; comp = new int[nVertices]; listaAdjacencias = new ArrayList<LinkedList<Ligacao>>(); for (int i = 0; i < nVertices; i++) { listaAdjacencias.add(new LinkedList<Ligacao>()); } //criar ligacao for (int i = 1; i < visit.length; i++) { visit[i] = false; } System.out.println("avenidas: "+this.avenidas); System.out.println("ruas: "+this.ruas); }
  6. algoritmos cyclicos

    Boas tardes, Alguem tem um bom exemplo ou conhece algum site sobre algoritmos de calculo de ciclos em grafos?
  7. Grafos

    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: 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 "nó") é 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: 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 Wikipedia: https://en.wikipedia.org/ USACO Training Program: http://train.usaco.org
×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade