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.

Filtrar por
Ordenado por
Com tags
-4 votos
1 resposta
39 visitas

Fiz um Grafo e queria Listar ele mas em Lista Adjacente

#include <iostream> #define max 10 using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ struct Grafo{ int ...
Gabriel Rodrigues's user avatar
-2 votos
1 resposta
74 visitas

Inserindo arestas em um grafo via lista de adjacência

Olá. Estou tentando programar meu primeiro grafo, via lista de adjacência. O resultado não está saindo como esperado, uma vez que não consigo obter o retorno da função inserir_aresta. O código simples ...
Quiet_waters's user avatar
-2 votos
1 resposta
231 visitas

Como ler adequadamente essa entrada para criação de um grafo em C?

Preciso fazer um trabalho na linguagem C onde a entrada é a quantidade de vértices de um grafo na primeira linha e para cada vértice é listado os nós adjacentes de cada vértice em cada linha, ...
Laura PS's user avatar
-1 votos
1 resposta
1mil visitas

Busca em profundidade python

Implemente um algoritmo que carregue um grafo direcionado e em seguida execute o algoritmo DFS no grafo carregado. Você pode armazenar o grafo na estrutura de dados que desejar; a. Use precedência ...
Keven Almeida's user avatar
0 votos
1 resposta
43 visitas

Agrupar vértices em função de weights

Com base num df de ligações pretendo selecionar todos os caminhos possíveis constituídos apenas por vértices cujas ligações verifiquem uma determinada condição neste caso valor >=3 library(igraph) ...
user250908's user avatar
-1 votos
2 respostas
38 visitas

Edges com valores incorretos

Ao rodar o código abaixo, não obtenho a representação gráfica esperada. Apesar de A estar ligado a C com valor 90.16 no plot a ligação A – C apresenta o valor 80. Alguém consegue ajudar? library(...
user250908's user avatar
1 voto
0 respostas
106 visitas

C++: Adicionar uma variável inteira de maneira ordenada em uma lista

Preciso adicionar inteiros de maneira ordenada, dentro de uma implementação de lista que eu desenvolvi. //Implementação dos nós para serem usados na lista NodeList::NodeList(int dataa){ this->...
Lucas Máximo Dantas's user avatar
-2 votos
1 resposta
201 visitas

Inserir aresta num grafo

Estou a tentar inserir uma aresta num grafo. O problema consiste em representar uma linha de metro, considerando a informação existente em ficheiros csv. Criei as classes Vertex, Edge, Station(Vertex),...
Sandra Silva's user avatar
1 voto
0 respostas
61 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 ...
Juliana's user avatar
  • 35
0 votos
1 resposta
423 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....
Gabriel's user avatar
-1 votos
1 resposta
370 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 ...
Mateus Dias's user avatar
-1 votos
1 resposta
655 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 ...
Luiz Falcão's user avatar
1 voto
0 respostas
382 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. ...
Luiz Falcão's user avatar
2 votos
0 respostas
195 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 ...
Williams Braga's user avatar
2 votos
1 resposta
1mil 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 ...
Gabriel Moura's user avatar
1 voto
1 resposta
340 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, ...
Gabriel Moura's user avatar
0 votos
1 resposta
276 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 ...
Igor Matsumoto's user avatar
14 votos
1 resposta
1mil 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 ...
Maniero's user avatar
  • 482mil
0 votos
0 respostas
338 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)...
Felipe Diniz's user avatar
0 votos
1 resposta
985 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 ...
Erik Jhonatta's user avatar
1 voto
0 respostas
132 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?
Eaken's user avatar
  • 11
1 voto
0 respostas
192 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, ...
Leila's user avatar
  • 1.314
4 votos
1 resposta
2mil 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(){ ...
ana lopes's user avatar
3 votos
1 resposta
574 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(...
Leila's user avatar
  • 1.314
0 votos
1 resposta
68 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 ...
Armando De Cabro's user avatar
5 votos
1 resposta
4mil 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 é ...
gato's user avatar
  • 23,7mil
5 votos
1 resposta
356 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 ...
Armando De Cabro's user avatar
1 voto
0 respostas
90 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 ...
Armando De Cabro's user avatar
0 votos
1 resposta
1mil 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 { ...
Amanda Nunes's user avatar
0 votos
0 respostas
110 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 ...
Lucas Pace's user avatar
2 votos
1 resposta
213 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. ...
Gabriel Yassunaga's user avatar
3 votos
2 respostas
154 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 ...
gato's user avatar
  • 23,7mil
1 voto
0 respostas
88 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 ...
NamelessBorneo's user avatar
0 votos
1 resposta
83 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=...
Overshell's user avatar
7 votos
1 resposta
216 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 ...
Rafael Paiva's user avatar
0 votos
1 resposta
496 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 ...
Lucas Vieira's user avatar
0 votos
0 respostas
218 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 ...
Eduardo Dutra's user avatar
2 votos
1 resposta
515 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 ...
HiHello's user avatar
  • 796
5 votos
1 resposta
2mil 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 ...
gato's user avatar
  • 23,7mil
1 voto
1 resposta
623 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 ...
Daniel Rosendo de Souza's user avatar
4 votos
1 resposta
866 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 ...
Vinicius Morais's user avatar
2 votos
3 respostas
1mil 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?
André's user avatar
  • 671
10 votos
1 resposta
264 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 ...
Jefferson Quesado's user avatar
18 votos
1 resposta
10mil visitas

O que é um banco de dados baseado em grafos? [duplicada]

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?
Bruno Peres's user avatar
  • 1.251
8 votos
2 respostas
1mil 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: ...
Bruno Peres's user avatar
  • 1.251
1 voto
0 respostas
815 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, ...
JoubertJoe .Vieira Lellis's user avatar
1 voto
0 respostas
12 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 ...
Isabela13's user avatar
4 votos
1 resposta
476 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 ...
Um Programador's user avatar
3 votos
2 respostas
3mil 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:
Thiago Pinho's user avatar
0 votos
1 resposta
256 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 ...
rodrigorf's user avatar
  • 1.029