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.
84
perguntas
-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 ...
-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 ...
-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, ...
-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 ...
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)
...
-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(...
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->...
-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),...
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 ...
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....
-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 ...
-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 ...
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. ...
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 ...
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 ...
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, ...
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 ...
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 ...
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)...
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 ...
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?
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, ...
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(){
...
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(...
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 ...
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 é ...
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 ...
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 ...
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 {
...
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 ...
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. ...
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 ...
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
...
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=...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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?
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:
...
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, ...
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 ...
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 ...
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:
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 ...