Perguntas com a tag [grafo]
A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas.
79
perguntas
-1
votos
0respostas
10 visitas
Grafos c++ - Estou instanciando uma list de uma classe e preciso criar um array dinamico pois minha entrada é pelo arquivo [fechada]
Estou fazendo um trabalho pratico sobre grafos e preciso colocar os vizinhos de um nó na lista e por isso pensei em fazer uma variável do seguinte tipo:
class.h
list class *array;
class.cpp (...
0
votos
0respostas
32 visitas
Eu estou entrando em um loop infinito mas não consigo achar o motivo
Eu basicamente tenho um grafo completo representado como lista de adjacência, eu tenho que achar entre todos os vértices um caminho entre um vértice especifico até algum vértice com interesse = 1 onde ...
0
votos
0respostas
15 visitas
GraphStream: como distanciar os nós?
Bom dia,
Ao criar meu grafo usando a API GraphStream , os nós são criados um em cima do outro.
Vi que existe uma propriedade na documentação em : layout.weight The force of repulsion of a node. The ...
1
voto
0respostas
22 visitas
Algoritmo Dijkstra com Priority Queue - comparator e poll não estão funcionando, minha lógica está errada?
Estou tentando aplicar o algoritmo de Dijkstra usando Priority queue
Preciso deixa-lo com complexidade logaritmica T(N) = E*log(n)
O primeiro nó consegue achar seus vizinhos e relaxar seus valores ...
0
votos
0respostas
115 visitas
Função Plot do igraph - (python)
Tentei usar a biblioteca do igraph para python a fim de plotar um grafo, usei o próprio exemplo da documentação, porém não deu certo.
Código usado:
import igraph
from igraph import plot
g = igraph....
-1
votos
1resposta
90 visitas
DIJKSTRA EM JAVA
Olá.
Estou implementando um grafo e como algoritmo de menor caminho, estou utilizando o DIJKSTRA.
O grafo indica a relação de gêneros e seus respectivos subgêneros.
O grafo é direcional, não ...
-1
votos
1resposta
94 visitas
Como descobrir todos os possíveis caminhos para visitar todos os vértices de um grafo? [fechada]
Preciso armazenar todas as possíveis rotas para visitar os vértices de um grafo sem passar por um mesmo vértice duas vezes (TSP), pensei em gerar as rotas aleatoriamente e armazenar todas que não ...
1
voto
0respostas
90 visitas
Caixeiro Viajante - Algoritmo Exaustivo [fechada]
Preciso criar um algoritmo que:
1. Descubra todos os possíveis caminhos que visitem todos os vértices de um grafo sem passar pelo mesmo vértices duas vezes.
2. Armazene todos os resultados.
3. ...
2
votos
0respostas
109 visitas
Preciso corrigir minha classe de Grafo em Python para simular um dicionário
Olá, eu estou tentando corrigir a minha classe de grafo para usar como um dicionário mais para frente, mas pelo que eu entendi ele só está acessando o local da memória ao invés dos dados, no exemplo ...
2
votos
1resposta
567 visitas
Implementação algoritmo Dijkstra em Python
Estou implementando o algoritmo de Dijkstra em um grafo, porém ele me retorna apenas a primeira chamada à função. Mesmo que eu chame novamente não há retorno, alguém sabe dizer o motivo?
Segue o ...
1
voto
1resposta
162 visitas
Adicionar tupla em conjunto Python
Estou criando um grafo com as seguintes regras:
O grafo é um dicionário.
Os vértices são as chaves desse dicionário e os valores são as arestas.
Como eu posso ter mais de uma aresta para um vértice, ...
0
votos
1resposta
103 visitas
Tentando construir um grafo
Bom pessoal, suponho que meu problema seja bem simples, mas estou com dificuldade, se puderem me ajudar eu agradeço!
O que eu quero é o seguinte: criar um vetor que consiga alocar vários caracteres ...
13
votos
1resposta
374 visitas
O que é Breadth First e Depth First?
Quando estamos lidando com árvores e grafos encontramos esses termos. O que eles significam e por que eles são importantes no uso de estruturas de dados destes tipos e algoritmos que as manipulam? O ...
0
votos
0respostas
144 visitas
Algoritimo Ford-Fulkerson Python
estou fazendo um trabalho de faculdade onde preciso implementar o algoritmo de Ford-Fulkerson em Python. Porém estou tendo dificuldade em achar um caminho aumentante no grafo residual (função caminho)...
0
votos
1resposta
155 visitas
Ler um arquivo texto e separar conteúdo em variáveis
Estou com uma dúvida em como dividir informações de um arquivo de texto em variáveis em C.
Exemplo, eu tenho um arquivo txt com os seguintes dados:
3 2
A
D
E
AD
DE
Gostaria de ler esse arquivo, e ...
1
voto
0respostas
78 visitas
Como escolher algoritmo de coloração entre Welsh/Powell e DSATUR?
Quando que eu devo usar Welsh/Powell e quando devo usar DSATUR?
Para que tipo de grafo cada algoritmo funciona melhor?
1
voto
0respostas
78 visitas
Passar números da entrada para matriz em Python
Estou fazendo um exercício sobre grafos bipartidos, no qual a entrada é dada na seguinte forma:
6
2 4 5
1 3
2 3 5
1 0
2 2 1
1 1
Sendo 6 (o número da primeira linha) o número de linhas a serem lidas, ...
4
votos
1resposta
882 visitas
Verificar se o grafo é conexo
Alguém me sabe dizer como posso implementar um método que me verifique se um grafo não direcionado é conexo e, caso não o seja, devolva os seus componentes conexos?
public void connectComps(){
...
3
votos
1resposta
338 visitas
Busca em Profundidade com Prolog - como limitar profundidade?
Estou implementando uma busca em profundidade em grafos em Prolog, já tenho o seguinte:
%arestas:
edge(c4,b4).
edge(b4,b3).
edge(b3,a3).
edge(b3,c3).
%determina que o grafo é nao direcionado
edge(...
0
votos
1resposta
45 visitas
Problema Relacionado a grafos
Estou fazendo esta questão no URI Online Judge.
Eu estou tentando com DFS, mas atá agora não consegui nada.
Botei uma variável pra marcar até o nível que ela vai e quando chegar nesse nível ela ...
4
votos
1resposta
2mil visitas
Como é o funcionamento básico do algoritmo A*?
Estou lendo a respeito do algoritmo de busca A* para poder implementa-lo futuramente. Eu sei que ele é usado para encontrar um caminho em um grafo, mas não consigo visualizar muito bem como isso é ...
5
votos
1resposta
155 visitas
Problemas com grafos em Java
Estou fazendo uma questão do URI e na entrada eles pedem assim.
Entrada: A entrada termina em EOF. Para cada caso de teste, a primeira linha contém dois inteiros positivos C e P que representam ...
1
voto
0respostas
47 visitas
Problema em classificar as Arestas dos grafos
Eu to fazendo um algoritmo para classificar as Arestas de um grafo, entre Tipo T, B ,C e F. Ele está me dando uma saída errada, ele termina o vértice 3 no mesmo tempo que começa o 4, então acaba não ...
-1
votos
1resposta
357 visitas
Fazer busca em profundidade usando uma pilha
Estou tentando fazer uma busca em profundidade usando uma pilha, mas está dando erro em um if e não sei o motivo.
package Grafos;
import java.io.*;
import java.util.*;
public class Grafo {
...
0
votos
0respostas
70 visitas
Lixo de memória ao apontar um ponteiro
Na tentativa de implementar um grafo de matriz adjacente, eu criei a função criarVertice no qual seria criada uma nova "matriz" e o conteúdo do grafo seria copiado para ela, adicionando as novas ...
2
votos
1resposta
101 visitas
Ponteiros de ponteiros em C
Bom galera, estou fazendo teoria dos grafos em C, e tentei usar alocação dinâmica para criar uma matriz. Além disso, meu código possui uma função para preencher a matriz com 1 nos índices recebidos. ...
3
votos
2respostas
101 visitas
Como associar objetos ao vértices de um grafo?
Estou estudando a respeito da teoria dos grafos, mais especificadamente sobre os vértices que são unidades que representam um determinado nó de um grafo. No entanto, ainda há algumas dúvidas em ...
1
voto
0respostas
45 visitas
Grafo representado como lista ligada a lista
Estou tentando implementar um grafo com estrutura de lista ligada a lista puxando os dados de um arquivo txt (entrada.txt).
A 100 2 B 3 D 4
B 150 2 C 3 E 2
C 150 1 F 2
D 150 1 E 4
E 100 1 F 1
F 200 0
...
0
votos
1resposta
65 visitas
Algoritmo de Kruskal ordenado com selection sort
Estou tentando comparar duas variáveis de um tipo struct, porém está retornando erro.
struct aresta{
int v1;
int v2;
int peso;
};
...
aresta peso[62816];
aresta aux;
int i, j=0;
for(i=...
6
votos
0respostas
120 visitas
Algoritmo de Christofides - TSP, Problema em transformar a AGM em um grafo com todos vértices com grau par
Estou realizando a implementação do algoritmo de Christofides e de entrada recebo os dados da TSPLIB.
o Algoritmo de Christofides tem os seguintes passos:
Achar a árvore geradora mínima
Achar todos ...
0
votos
1resposta
68 visitas
Qual software usar para gerar uma imagem de um grafo gigante?
Tenho um programa em c++, feito com a representação de grafos com lista de adjacência, porém, existem mais de 2 milhões de nós nele.
Existe algum software que tenha um formato de texto, que eu possa ...
0
votos
0respostas
119 visitas
C - Stack Smashing Detected - Como inicializar corretamente um grafo por lista de adjacência e inserir arestas?
Estou recebendo, esporadicamente e sem ter feito qualquer alteração no código ou na entrada, um erro chamado Stack Smashing Detected.
As únicas coisas que estou fazendo é inicializar um grafo e ...
2
votos
1resposta
190 visitas
Eliminar ciclos em grafo removendo menos vértices
Gostaria de saber se alguém sabe se é possível eliminar todos os ciclos de um grafo não-direcionado (n vértices) sem pesos, removendo o menor número de vértices, em tempo O(n²)?
Obs: O grafo pode ...
5
votos
1resposta
971 visitas
O que é uma Matriz de Adjacência?
Sempre que leio algo em relação a teoria dos grafos eu esbarro com um termo chamado Matriz de Adjacência, me parece que isso esta fortemente relacionado com esta teoria. Sendo assim, eu gostaria de ...
1
voto
1resposta
420 visitas
Algoritmo Grafos para resolver Sudoku
Estou com uma duvida, meu código quando ele é executado em um dos exemplos de Sudoku, ele printa no final o resultado esperado, o outro exemplo de sudoku ele não imprime corretamente o resultado ...
3
votos
1resposta
477 visitas
Existe uma forma melhor de construir um grafo?
Possuo uma lista de artigos com suas respectivas tags:
artigo1 ['a','b','c']
artigo2 ['a','d','f']
artigo3 ['z','d','f']
...
Preciso criar um grafo que irá relacionar todos os artigos pelas tags. No ...
2
votos
3respostas
558 visitas
Remoção árvore binária
Pessoal como fica a árvore após a remocão do número 40?
No meu entendimento, no lugar do 40 seria o número 41, direita 44 e esquerda 30. E a direita do 44 o número 49, to certo?
10
votos
1resposta
160 visitas
Como identificar um grafo inválido para problema de alocação de operadores por máquina?
Recentemente estava respondendo uma questão (Escalonamento de máquinas - Teoria dos Grafos), porém ficou um problema em aberto que não consegui resolver:
Dado um grafo qualquer, identificar se ...
17
votos
1resposta
6mil visitas
O que é um banco de dados baseado em grafos?
Não encontrei neste site a resposta para esta pergunta. Então, minha questão é basicamente esta:
O que é um banco de dados baseado em grafos?
7
votos
2respostas
787 visitas
Quais são os cenários apropriados para bancos de dados baseados em grafos
Ultimamente tenho estudado o banco de dados baseado em grafos Neo4j.
Tendo em vista que a grande maioria das aplicações atuais utilizam-se de bancos de dados relacionais tradicionais, pergunto:
...
1
voto
0respostas
377 visitas
Busca em Largura e Profundidade num grafo [fechada]
Eu preciso implementar um sistema de visitas, e a busca em Largura (grafos).
Como proceder?
[EDIT]
Eu hostaria de saber a melhor forma de fazer com que esse algorítimo funcione também para Grafo, ...
1
voto
0respostas
7 visitas
Criar linha no TSimpleGraph
Boa tarde.
Estou utilizando o TSimpleGraph para criar grafos no meu programa. Gostaria de criar uma linha horizontal através do código, escolhendo sua posição no form. . Gostaria também que ela fosse ...
4
votos
1resposta
307 visitas
Qual é a diferença principal entre os algoritmos Knuth-Morris-Pratt e Boyer-Moore
Eu sei que o KMP(Knuth-Morris-Pratt) é utilizado para achar um texto Y em X, tenta definir um padrão em Y, e depois salva este padrão em um vetor. E eu sei também que o BM(Boyer-Moore) funciona melhor ...
0
votos
1resposta
760 visitas
Como utilizar o Algoritmo de Verificação de Ciclo em Grafos?
Olá, gostaria de saber como utilizar o Algoritmo de Verificação de Ciclo em Grafos para encontrar uma condição cíclica, se puder me colocar a utilização do algoritmo neste Grafo abaixo:
0
votos
1resposta
166 visitas
Alterar cor de um nó em um grafo do Neo4J
Criei um grafo de exemplo no Neo4J com um pai e dois filhos. Gostaria de saber como alterar a cor de todos os nós que tenham o nível igual a 1.
Quando clico no nó aparece na parte de baixo para ...
5
votos
1resposta
265 visitas
Escalonamento de máquinas - Teoria dos Grafos
estou fazendo uma lista de exercícios de teoria dos grafos e empaquei em uma questão que tem o seguinte enunciado:
São dadas máquinas 1, . . . , n e intervalos de tempo I1, . . . , In.
Para cada ...
0
votos
1resposta
499 visitas
Como verificar se o valor de uma key existe em um mapa em c++
Estou fazendo um TAD de grafos e uso uma estrutura map para mapear o ID de um vértice para o seu índice na matriz de adjacências e para fazer isso eu preciso antes verificar se dado o id do vértice ...
2
votos
1resposta
974 visitas
Todos possíveis caminhos em grafos
estou fazendo um trabalho que parte dele consiste em achar todos os possíveis caminhos a partir de um vértice até um outro determinado vértice, para isso estou usando um algoritmo quase idêntico a DFS ...
15
votos
1resposta
7mil visitas
Algoritmo de Prim e Kruskal
Os dois algoritmos servem para gerar uma Árvore Geradora Mínima de um Grafo.
No Prim
Gera uma árvore única
Ao longo do algoritmo, o conjunto X sempre é uma árvore
No Kruskal
Gera uma floresta, ...
0
votos
1resposta
110 visitas
Criar Grafos com TSimpleGraph
Estou precisando criar grafos na interface do meu programa,
a única solução que encontrei foi o TSimpleGraph. Tentei rodar o programa que vem no arquivo ZIP, porém dá erro que está faltando o ...