Respostas interessantes marcadas com a tag

19 votos

Desafio da Colônia de Formigas

Pelo texto do problema, estou supondo que a origem é este site: http://br.spoj.com/problems/ANTS10/ Conforme os comentários: do @gabriel: trata-se de um problema que envolve a teoria dos ...
Gomiero's user avatar
  • 5.421
14 votos

O que é um banco de dados baseado em grafos?

Diferente dos bancos de dados relacionais o Banco de dados orientado a grafos possui outras formas de persistência de dados o NoSQL. A ideia é criar um modelo menos genérico que o modelo relacional, ...
Caique Romero's user avatar
12 votos
Aceito

O que é Breadth First e Depth First?

Breadth first e depth first são duas estratégias de busca semelhantes, porém distintas. Normalmente você encontra o termo completo: BFS ou DFS, onde o S da sigla significa search. Seus significados ...
Jefferson Quesado's user avatar
9 votos
Aceito

Diferença na aplicação dos algoritmos de Dijkstra e Prim

O algoritmo original proposto por Dijkstra serve para achar o menor caminho de um nó inicial até um nó final. Porém o algoritmo de Dijkstra mais utilizado é uma variante que acha o menor caminho de um ...
Sérgio Mucciaccia's user avatar
8 votos
Aceito

Algoritmo de Prim e Kruskal

Algumas diferenças entre os algoritmos: O algoritmo de Prim inicializa com um nó, enquanto o algoritmo de Kruskal inicia com uma aresta ordenada. No algoritmo de Prim, o grafo deve ser conectado, ...
Taisbevalle's user avatar
  • 9.154
6 votos
Aceito

Verificar se o grafo é conexo

Como a dúvida se trata de grafos não direcionados, estou usando isso como premissa em toda a minha resposta. Tudo que eu escrever vale para grafos não direcionados, exceto se você encontrar alguma ...
Jefferson Quesado's user avatar
5 votos

Desafio da Colônia de Formigas

Complementando a excelente resposta do @Gomiero, você realmente pode utilizar uma simples árvore para representar as conexões entre os formigueiros, tendo o formigueiro de número 0 como o nó raiz da ...
tayllan's user avatar
  • 2.493
5 votos

Como utilizar o Algoritmo de Verificação de Ciclo em Grafos?

Existem vários algoritmos que podem ser usados para identificar ciclos em grafos. O mais simples é a busca em produndidade (DFS na sigla em inglês). Basta implementar uma busca em profundidade que ...
Gabriel's user avatar
  • 1.915
5 votos
Aceito

Lista sendo modificada sem implementação

O problema ocorre no trecho abaixo: lista_inicial = [[1, 2], [0, 2], [0, 1]] lista_aux = [] lista_aux = lista_inicial # Aqui! Ao fazer lista_aux = lista_inicial você está indicando que lista_aux ...
stderr's user avatar
  • 30,8mil
5 votos
Aceito

O que é uma Matriz de Adjacência?

O que é a Matriz de Adjacência? A grosso modo, é uma matriz de booleanos acessado de maneira direta. Dado um grafo com n vértices, a matriz de adjacências é uma matriz booleana de n*n casas. Se há ...
Jefferson Quesado's user avatar
4 votos

Existe APIs de interface gráfica para Grafos no android?

Para realizar a plotagem dos grafos no Android, você pode usar essas bibliotecas: MPAndroidChart - Poderosa biblioteca para visualização de grafos e gráficos AChartEngine - Biblioteca gráfica para ...
regmoraes's user avatar
  • 2.961
4 votos

Quais são os cenários apropriados para bancos de dados baseados em grafos

Nenhum :P Claro que há. A questão é que é possível usar o banco de dados relacional para fazer grafos já que estes estão em um nível acima do relacional e cada vez mais os principais softwares de ...
Maniero's user avatar
  • 482mil
4 votos
Aceito

Como identificar um grafo inválido para problema de alocação de operadores por máquina?

Conforme percebido pelos usuários no MathExchange, meu problema se trata na detecção de um grafo de intervalo. Particularmente não consegui entender os algoritmos disponíveis na internet sobre o ...
Jefferson Quesado's user avatar
4 votos
Aceito

Fazer busca em profundidade usando uma pilha

O procedimento deveria ser mais ou menos assim: Insere o primeiro nó na pilha e marca como visitado. Enquanto houver nós na pilha, desempilha o nó e empilha todos os seus vizinhos que não tiverem ...
Victor Stafusa - BozoNaCadeia's user avatar
4 votos
Aceito

Como é o funcionamento básico do algoritmo A*?

Como o algoritmo A* consegue encontrar caminhos em um grafo? O algoritmo recebe: o grafo o nodo inicial o nodo final uma função de heurística Começando pelo nodo inicial, ele pega todos os ...
Gabriel's user avatar
  • 1.915
3 votos
Aceito

Existe uma forma melhor de construir um grafo?

Conforme eu tinha comentado, eu fiz um esquema de montagem de grafos em Java baseado em mapas, desde que cada nó tivesse uma chave que o identificasse. O seu caso é ligeiramente diferente, pois cada ...
Jefferson Quesado's user avatar
3 votos
Aceito

Escalonamento de máquinas - Teoria dos Grafos

Vou dever as imagens, mas vou responder o melhor possível textualmente Você está trabalhando com um problema de otimização. No caso específico, você quer minimizar a quantidade de operadores. ...
Jefferson Quesado's user avatar
3 votos
Aceito

Busca em grafos para resolver o teorema de euler

Para determinar se o grafo é conexo, a melhor abordagem provavelmente é a busca em largura ou em profundidade. (Referência) Para contar o grau de cada vértice, você pode usar lista de adjacências ou ...
Victor Stafusa - BozoNaCadeia's user avatar
3 votos
Aceito

Caminho entre 2 nos de um grafo usando menor numero de arestas coloridas

A primeira coisa que você deve perceber no problema é que o custo entre as diversas linhas de ônibus é sempre 1, então você não precisa nem mesmo utilizar o algoritmo de Dijkstra ou qualquer outro ...
tayllan's user avatar
  • 2.493
3 votos
Aceito

Ponteiros de ponteiros em C

Atenção a este tipo de typedefs: typedef struct digraph* Digraph; Deve evitar este tipo de typedefs com ponteiros pois eles acabam a mascarar os tipos e dar lhe a ideia errada, consequentemente ...
Isac's user avatar
  • 25,4mil
3 votos
Aceito

Busca em Profundidade com Prolog - como limitar profundidade?

Na realidade, ao utilizar History e verificar se o nó já faz ou não parte de History, você já está limitando a busca e evitando nós repetidos. Não é necessário limitar artificialmente a profundidade (...
mgibsonbr's user avatar
  • 82,5mil
3 votos
Aceito

Edges com valores incorretos

Você está plotando o grafo simplificado, mas fornecendo para o rótulo os valores do grafo completo. Coloque o grafo simplificado em um novo objeto, indicando para o simplify o que fazer com atributos ...
Carlos Eduardo Lagosta's user avatar
2 votos

Importar .sql do PostgreSQL no Neo4j

O @BrunoRB está correto, você vai precisar em algum momento criar uma função de mapeamento Modelo Relacional <--> Grafo dos seus dados. Este tutorial da Neo4j pode ajudá-la. Simplificando o ...
tayllan's user avatar
  • 2.493
2 votos

Como limpar as properties do neo4j depois de deletado todos os dados?

Você deve ser capaz de limpar tudo por: Parar o seu banco de dados Neo4j Excluindo dodos os dados correspondentes / graph.db / * (procure dentro da pasta graph.db) Reativar o banco de dados
Evelym's user avatar
  • 53
2 votos

Ciclo hamiltoniano demorando demais

Determinar se um grafo possui um ciclo hamiltoniano é um problema NP-Completo (Fonte: Wikipedia). Problema NP-Completo significa que não há algoritmo polinomial conhecido para encontrar uma solução (...
Rafael B.'s user avatar
  • 507
2 votos
Aceito

"Juntar" dois grafos em R

O código abaixo resolve o teu problema. Inclusive, ele seleciona aleatoriamente um dos vértices do g.v1 para fazer a ligação com o grafo g.merchant. library(igraph) g.v1 <- graph.full(6, directed=...
Marcus Nunes's user avatar
  • 18,9mil
2 votos
Aceito

Como verificar se o valor de uma key existe em um mapa em c++

Basta usar o método find do std::map. Isso vai retornar um iterador, se o iterador não for igual ao end() do seu map, então quer dizer que o valor da key existe. Exemplo: #include <iostream> #...
Ossetian_Odin's user avatar
2 votos
Aceito

Qual é a diferença principal entre os algoritmos Knuth-Morris-Pratt e Boyer-Moore

Exemplo funcional em inglês Knuth-Pratt-Morris Boyer-Moore Em uma explicação grosseira A abordagem de Boyer-Moore é tentar combinar o último caractere do padrão em vez do primeiro com a suposição ...
Um Programador's user avatar
2 votos
Aceito

Como associar objetos ao vértices de um grafo?

Veja se esta solução lhe agrada: class Ambiente: def __init__(self, titulo, descricao, id): self.titulo = titulo self.descricao = descricao self.id = id A = Ambiente('Sala de maquinas',...
AlexCiuffa's user avatar
  • 2.439
2 votos
Aceito

Tentando construir um grafo

Você declarou V como um int mas leu ele como um long, o correto seria ler como um inteiro (scanf("%d", &V)) ou declarar V como um long (long V;) Um outro ponto, você provavelmente vai ter ...
capaci's user avatar
  • 106

Only top scored, non community-wiki answers of a minimum length are eligible