Most voted "graph" questions
Graph theory is a branch of mathematics that studies the relationships between the objects of a given set. For this are employed structures called graphs, G(V,A), where V is a nonempty set of objects called vertices and A is a set of unordered pairs of V, called edges.
Learn more…82 questions
Sort by count of
-
29
votes2
answers1063
viewsChallenge of the Ant Colony
I have a programming marathon problem and I want to know if my solution is right, as well as improvement suggestions. Problem A group of ants are really proud because they have built a magnificent…
-
18
votes1
answer8163
viewsWhat is a graph-based database?
I did not find on this site the answer to this question. So my question is basically this: What is a graph-based database?
-
17
votes1
answer8180
viewsWhat is a minimal generating tree?
I have an exercise to solve and the teacher told me that I would just use this method to solve. What is a minimal generating tree and how can I use it in practice?
-
15
votes1
answer7529
viewsPrim and Kruskal algorithm
The two algorithms serve to generate a Minimum Generating Tree of a Graph. In the Prim Generates a single tree Throughout the algorithm, the set X is always a tree In the Kruskal Generates a forest,…
graphasked 7 years ago Don't Panic 4,006 -
12
votes1
answer517
viewsWhat’s Breadth First and Depth First?
When we are dealing with trees and graphs we find these terms. What do they mean and why are they important in using data structures of these types and algorithms that manipulate them? What I gain…
-
10
votes1
answer187
viewsHow to identify an invalid graph for operator allocation problem per machine?
Recently I was answering a question (Machine Scheduling - Graph Theory), but there was an open problem that I could not solve: Given any graph, identify if it is valid for the operator allocation…
-
7
votes1
answer2359
viewsDifference in the application of Dijkstra and Prim algorithms
What is the basic difference in the field of application of Dijsktra and Prim algorithms? What problems does one solve that the other cannot solve? Having, for example, the following situation: it…
-
7
votes2
answers767
viewsPath between 2 nos of a graph using smaller number of colored edges
I’m trying to solve this programming problem. In summary, the problem describes several bus lines as an undirected graph and says that a bus ticket costs 1 real. Can someone give me a hint on how I…
-
7
votes1
answer355
viewsHamiltonian cycle taking too long
I have to find out if there is Hamiltonian cycle in a giant graph (1000 vertices in the smallest instance and 5000 vertices in the largest). My initial idea was to backtrack, and in small instances,…
-
7
votes2
answers985
viewsWhat are the appropriate scenarios for graph-based databases
Lately I’ve been studying the graph-based database Neo4j. Given that the vast majority of current applications use traditional relational databases, I ask: What are the appropriate scenarios to use…
-
6
votes0
answers145
viewsAlgorithm by Christofides - TSP, Problem in transforming the AGM into a graph with all vertices with even degree
I am carrying out the implementation of the algorithm of Christofides and input I receive the data from TSPLIB. Christofides' Algorithm has the following steps: Find the minimum generating tree Find…
-
5
votes1
answer1239
viewsWhat is an Adjacency Matrix?
Whenever read something in relation to graph theory I stumble upon a term called Adjacency matrix, it seems to me that this is strongly related to this theory. Therefore, I would like to know more…
-
5
votes1
answer279
viewsMachine Scheduling - Graph Theory
I am making a list of graph theory exercises and I have enclosed in a question that has the following statement: Machines are given 1, . . . , n and time intervals I1, . . . , In. For each i, an…
-
5
votes1
answer186
viewsProblems with graphs in Java
I’m making a URI issue and in the lobby they ask so. Input: The input ends in EOF. For each test case, the first line contains two positive integers C and P that represent respectively the number of…
-
4
votes1
answer491
viewsFind isolated components in graph
What is the best algorithm for finding isolated components in a graph? That is, components that do not lose information. In this image, the only isolated component is H, because it only receives…
-
4
votes1
answer250
viewsIs it possible to use vertical, edge or face coloring in a DIRECTED graph?
I would like to know if it is possible to use the staining technique in directed graphs? Whether yes or no, why?
graphasked 9 years ago William Pereira 3,998 -
4
votes2
answers6881
viewsGraph possible python paths
I have a dictionary, where the key is a vertex and the value is a list of vertices adjacent to the vertex (key). dic = {'A':['B,'C'],'B':['A','C','D'],'C':['A','B','D'],'D':['B','C']} What I want is…
-
4
votes2
answers300
viewsImport . sql from Postgresql in Neo4j
I have a Postgresql . sql backup file and want to import that file to Neo4j (graph database). How do I?
-
4
votes1
answer359
viewsWhat is the main difference between the Knuth-Morris-Pratt and Boyer-Moore algorithms
I know that the KMP(Knuth-Morris-Pratt) is used to find a Y text in X, tries to define a pattern in Y, and then saves this pattern in an array. And I also know that the BM(Boyer-Moore) works best…
-
4
votes1
answer77
viewsList being modified without implementation
I’m having a problem where the list I’m working on is being modified even though there’s no value passing to it. from random import * from numpy import * m=2 lista_inicial=[[1, 2], [0, 2], [0, 1]]…
-
4
votes1
answer553
viewsIs there a better way to build a graph?
I have a list of articles with their respective tags: artigo1 ['a','b','c'] artigo2 ['a','d','f'] artigo3 ['z','d','f'] ... I need to create a graph that will relate all articles by tags. In the end…
-
4
votes1
answer1169
viewsCheck that the graph is connected
Can anyone tell me how I can implement a method that checks me if an undirected graph is connected and, if not, returns its related components? public void connectComps(){…
-
4
votes1
answer2544
viewsHow is the basic functioning of algorithm A*?
I’m reading regarding the search algorithm A* to be able to implement it in the future. I know it’s used to find a path in a graph, but I can’t visualize very well how it’s done. However, I am…
-
3
votes1
answer1597
viewsKruskal’s algorithm problem C++
I’m implementing Kruskal’s algorithm, only I’m having a problem because he’s missing one of the links and the value of it, I’ve already made an implementation in Dijkstra, only in the work I’m doing…
-
3
votes1
answer237
views"Join" two graphs in R
I’m using the library igraph to create two graphs in R: g.v1 <- graph.full(6, directed= TRUE) E(g.v1)$weight <- 1 g.merchant <- graph.empty(1, directed=TRUE) E(g.merchant)$weight <- 1…
-
3
votes1
answer2865
viewsDoubt in the implementation of the deep search in Graphs
I’m studying for a proof of algorithms and I ended up finding some problems to implement the DFS(Depht-First Search/deep search) using data structure Stack. static void…
-
3
votes0
answers2685
viewsAlgorithm by Dijkstra
I’m trying to implement a maze, where one needs to find a better way to get to the exit (without running into the wall). The labyrinth has already been implemented, the structure is practically…
-
3
votes2
answers1275
viewsHow to use the Graph Cycle Verification Algorithm?
Hello, I would like to know how to use the Graph Cycle Check Algorithm to find a cyclic condition, if you can put me the use of the algorithm in this graph below:…
-
3
votes1
answer252
viewsSearching graphs to solve Euler’s theorem
Hello, I would like a help to do a search on a graph and check if it satisfies the theorem of Euler. The theorem says: "A connected graph will contain an Euler cycle if, and only if, each vertex has…
-
3
votes2
answers110
viewsHow to associate objects to the vertices of a graph?
I’m studying about graph theory, more specifically about vertices which are units representing a given node of a graph. However, there are still some doubts regarding the vertices. See this…
-
3
votes1
answer408
viewsDepth Search with Prolog - how to limit depth?
I am implementing an in-depth graph search in Prolog, I already have the following: %arestas: edge(c4,b4). edge(b4,b3). edge(b3,a3). edge(b3,c3). %determina que o grafo é nao direcionado edge(V1,…
-
2
votes2
answers697
viewsHow do I find the smallest cycle of an undirected graph?
I can find a cycle in an undirected graph. But I can’t think of a way to list the vertices of each cycle, and not even find the smallest cycle. How do I do this?
graphasked 9 years, 5 months ago SakataGintoki 21 -
2
votes2
answers193
viewsSegmentation fault in C: Adjacency structure representing graph
I need to create a program to read a graph and represent in an adjacency structure, however, my compiler is accusing Segmentation fault and I can’t figure out what might be causing it. It might help…
-
2
votes1
answer60
viewsChecks for a vertex in R
I am using igraph on R. I have the following graph: Is there any function in R, which returns me a boolean value, which verifies the existence of a vertex?…
-
2
votes1
answer794
viewsHow to generate Adjacent Matrix of a BFS from a txt file? C++
I’m using the Codeblocks. I have a. txt file that represents a maze, everything that is after the : are rooms: The first line of the file shows the start coordinate, which in this case is AS. Every…
-
2
votes3
answers649
viewsBinary tree removal
Personal as the tree looks after the removal of the number 40? In my understanding, instead of 40 would be number 41, right 44 and left 30. And the right of the 44 the number 49, to right?…
-
2
votes1
answer269
viewsEliminate cycles in graph by removing fewer vertices
I wonder if anyone knows if it is possible to eliminate all cycles of an undirected graph (n vertices) weightless, removing the smallest number of vertices, in time O(n²)? Note: The graph can be…
-
2
votes1
answer1127
viewsAll possible paths in graphs
I am doing a work that part of it consists of finding all possible paths from one vertex to another given vertex, for this I am using an algorithm almost identical to DFS as shown below: #include…
-
2
votes1
answer131
viewsC pointers
Well, guys, I’m doing graph theory on C, and I tried to use dynamic allocation to create an array. Also, my code has a function to fill the matrix with 1 in the received indexes. But I have some…
-
2
votes1
answer842
viewsImplementation Dijkstra algorithm in Python
I am implementing Dijkstra’s algorithm in a graph, but it returns only the first call to the function. Even if I call again there is no return, does anyone know why? Follows the code: def…
-
2
votes0
answers144
viewsI need to fix my Python Graph class to simulate a dictionary
Hello, I am trying to fix my graph class to use as a dictionary further forward, but from what I understand it is only accessing the memory location instead of the data, in the example below I will…
-
1
votes0
answers239
viewsWidth Search and Depth Search
I am studying for the Programming Marathon and I need examples of searching in width/ searching in graph depth
-
1
votes0
answers7
viewsCreate line in Tsimplegraph
Good afternoon. I’m using Tsimplegraph to create graphs in my program. I would like to create a horizontal line through the code by choosing its position in the form. . I would also like it to be…
-
1
votes2
answers418
viewsHow to clear neo4j properties after deleted all data?
I was doing some tests with the neo4j and suddenly I saw myself before many us and then I decided to clean everything, so I could start working with an application. So I executed the following…
-
1
votes0
answers186
viewsHelp with using the igraph and timeorded library in R
I’m using the lib 'igraph' and 'timeorded' (http://www.benjaminblonder.org/timeorderednetworks/) to work with time graphs. I have the following time graph: "graph.txt": a c 1 1 a d 2 2 b d 2 2 c d 3…
-
1
votes0
answers62
viewsget.shortest.paths in time graph
I’m using the "igraph" library and I’m working with dynamic graphs. I have the following graph: VertexFrom VertexTo TimeStart TimeStop to c 1 1 a d 2 2 b d 2 2 c d 3 3 d b 3 That is, v1 is connected…
-
1
votes1
answer677
viewsProblem to insert a graph
I’m trying to insert vertices and links into a graph, but it only works when the graph has an even number of edges. The source code below has the TAD and the functions of inserting and creating…
-
1
votes1
answer2433
viewsGraph using python-igraph with attributes per node and edges
Talk people! I’m trying to create a graph using the Python-Igraph library. Each node would have an attribute, for example, in a book graph whose nodes would be books and the attributes of those…
-
1
votes0
answers495
viewsSearch Width and Depth in a graph
I need to implement a system of visits, and the search in Width (graphs). How to proceed? [EDIT] I would like to know the best way to make this algorithm work for Graph as well, because it is…
-
1
votes0
answers91
viewsHow to choose coloring algorithm between Welsh/Powell and DSATUR?
When should I use Welsh/Powell and when should I use DSATUR? For what type of graph each algorithm works best?