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 ...
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, ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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á ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 (...
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 ...
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 ...
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
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 (...
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=...
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>
#...
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 ...
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',...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Tags relacionadas
grafo × 86c × 16
algoritmo × 14
python × 12
java × 11
c++ × 9
r × 8
estrutura-de-dados × 8
python-3.x × 5
ponteiro × 4
neo4j × 4
algoritmo-de-busca × 4
banco-de-dados × 3
matriz × 3
matemática × 3
dicionário × 3
python-igraph × 3
string × 2
lista × 2
arquivo × 2
terminologia × 2
lógica × 2
stack × 2
nosql × 2
complexidade-de-algoritmo × 2