# Questions tagged [graph]

A graph is an abstract representation of objects (vertices) connected by links (edges). For questions about plotting data graphically, use the [data-visualization] tag instead.

584 questions
Filter by
Sorted by
Tagged with
7k views

### Graph and minimum spanning tree in Python

Here is my Graph class that implements a graph and has nice a method to generate its spanning tree using Kruskal's algorithm. I want to: Make it pythonic Improve readability Improve the abstraction (...
6k views

### Find shortest paths in a matrix using Dijkstra's algorithm

The problem is as follows: I have a matrix with impassable fields those are marked by the input. There is also a castle which reaches up the right side of the matrix. I have to find how many paths ...
809 views

### Maxflow for baseball elimination game

I have a problem similar to the baseball elimination. Given some teams, the number of wins they have and the number of games they have left between each other I have to find for which team it is still ...
617 views

### Comparing linear time strongly connected component algorithms in Java

So I have implemented three linear time ($\mathcal{O}(V + E)$) algorithms for finding strongly connected components of a (directed) graph. A strongly connected component is just a maximal subset of ...
751 views

### Optimizing and accounting for edge cases in Dijkstra's algorithm

I just recently wrote a program to simulate how multicast routing works. The program uses a weighted graph to represent the network and simply runs it through the algorithm. I would like to know if ...
34 views

### Data Explorer query that makes bar graphs

I wrote a query for SEDE that I think is pretty cool. It uses the currently available graphing capabilities (scatter plots) to create a bar graph. I have used it as the subject for a self-answer on ...
537 views

### Pseudo-parallel depth-first search

I'm writing a small program that generates a file containing an adjancency matrix, it then reads from that file, constructs a graph and does something like a parallel depth-first search (dfs) on it. ...
65 views

### Social network graph of characters in a novel

I wrote a C program that builds a social network graph of characters in a novel. The program takes two text files as input: a list of the names of the characters in the novel, and the file of the ...
4k views

### Implementation of Dijkstra's algorithm in C++

This is my implementation of Dijkstra's algorithm. Could you tell me what am I doing wrong and what should be fixed? I was not sure how to keep track of the shortest outgoing edge from a node and I ...
2k views

### Implementation of Prim's algorithm in C++

Could anyone comment on what could be done better and if I made any mistakes? ...
1k views

### Topological sort using recursive DFS

I am currently learning Graph algorithms by solving questions on online judges. The below code is for implementing Topological sort, using recursive DFS. Also, it is my first time with C++ STL. ...
969 views

### Idiomatic ruby to calculate distance to points on a graph

Can this code be made more like idiomatic ruby using methods such as map or inject? @random_tour is a variable length array of points on a graph: ...
194 views

### Simple graph in Rust

I have written simple code to construct a graph, but I think there are too many different types for such a simple task. In this code I need to store Node structs ...
2k views

### Detect cycle in undirected graph

Below is my code to detect cycle in an undirected graph. Could anyone please review and let me know if I have taken care of all the cases? The basic idea is to use DFS (non-recursive using stack) and ...
2k views

### Finding all paths between nodes in a graph

I wanted to write a function paths that returns the possible routes between two nodes in a graph. For example: ...
2k views

### Dijkstra's algorithm: traditional and bidirectional in Python

I have translated Dijkstra's algorithms (uni- and bidirectional variants) from Java to Python, eventually coming up with this: Dijkstra.py ...
4k views

### Simple weighted directed graph in Python

I have this simplistic Python class for representing directed weighted graphs (digraphs for short): Digraph.py ...
3k views

### Graph Library in C

Could you guys please review the Graph Library I developed in C? It's also on GitHub ...
65 views

### Minimum number of moves to reach the end - follow-up

I need to calculate the minimum number of jumps to reach the end of an array with dice throws. Array values may be negative/positive: When positive - move forward When negative - go back The array ...
157 views

### Minimum number of moves to reach the end

I need to calculate the minimum number of jumps to reach the end of an Array with dice throw. Array values may be negative/positive: When positive - move forward When negative - go back The array ...
1k views

### Task scheduler with dependencies

I have need for a task scheduler determined by a directed graph. The tasks are held in a std::vector<task_type>, while the dependency graph is held in a ...
3k views

### Implementation of Dijkstra's Algorithm in JavaScript that returns both shortestDist/shortestPaths

I decided to try to understand the basic idea behind Dijkstra's algorithm better so I implemented it in JavaScript (the only language I am proficient in as of now) so I could really see what was ...
46 views

### Distributed (asynchronous) averaging

This code simulates a distributed averaging protocol. There is a network of nodes, and at the clicks of a Poisson process: A random node wakes up Transmits it's current average to all the nodes it is ...
714 views

### Using the A* algorithm to search a graph generated from a grid

Following on from my previous question, I finally got round to actually doing the A* search for the Graph<MapTile>. The changes to the code from the previous ...
190 views

### DFS algorithm too slow

I am practicing my coding on leetcode, and my submission, although correct for small cases, is timing out for large ones. Could you please let me know how to improve my code? The question is as ...
318 views

### Generating a graph from a rectangular grid for graph searching

I recently reviewed some code implementing some heuristics which has piqued my interest in the A* graph searching algorithm. I'm going to do that in a bit but first I need a way to create a graph in ...
8k views

### A graph representation of Adjacent Matrix in Python

I'm trying to create a graph representation in Adj Matrix in Python. I'm not sure if this is the best pythonic way. ...
501 views

### Check if the undirected graph is cyclic

Here is my approach. Do DFS and check in stack whether the new node is already in the Stack or not. ...
489 views

### Check directed graph is tree or not

Here is my approach. 1. Checking there is no cycle.(Using BFS) 2. All nodes are connected. (visited) ...
1k views

### CLRS(Introduction To Algorithms) implementation of BFS and DFS in Java

This is the implementation of BFS and DFS i have tried to follow from CLRS.Please suggest what can be improved in this code. ...
105 views

### Check if path exists directed graph, without using collection

I have written code to find whether the path exists between source and destination in a directed graph. I have used BFS and instead of ArrayList or queue. I have ...
108 views

### Find the largest continuous descending sum in a 2d matrix

Given a 2d array, the problem is to find the largest sum, where each subsequent is >= the previous digit but < all of the 'neighbour' digits. You can only move up, down, left and right. My ...
168 views

### Finding smallest number of moves

We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this: ...
462 views

### “Researcher Hatim is right or wrong” challenge

I wrote a program to solve a problem, I am not so good in python so want help to find areas where this program can be improved or simplified and readable too:- I got this problem in a code challenge ...
441 views

### Find all the countries I can visit by just crossing direct borders

I was helping on this question. There you have a table border to indicate countryA and countryB have a common border. And want ...
112 views

### Computing the distance and weight matrix of a graph

I would like to create an igraph object. First, I set up the size of igraph object — n, m, then create a random matrix. As a result matrix ...
690 views

### Dijkstra algorithm implementation in F#

I'm trying to implement Dijkstra algorithm in F# for finding the shortest path in a undirected tree using a heap. I've used the type PriorityQueue found here and the code can be found here. ...
797 views

### Dynamic graph in C++11 with shortest path algorithm

I've been designing a dynamic graph to improve my understanding of C++11. The dynamic aspect means that it could represent the hyperlink structure of a chunk of the internet, with node deletion ...
214 views

### Glue Shredded Pieces (CodeEval)

I have solved problem 185 on CodeEval, Glue Shredded Pieces. The solution got a 100% score on all tests (edit: see comments), within the allotted time and memory constraints. I'm looking mostly ...
2k views

### Iterative depth-first search and topological sort in Java

This is the iterative depth-first search, that does not abuse the stack. Also, I gathered some information from DFS that may be useful; for example, I am able to do topological sort using the result ...
1k views

### Check if a given path exists in a graph

I'm using BFS to see if a given path exists in a graph: ...
2k views

### Simple data structures for representing graphs in Java

Motivation I do a lot of graph-theoretic code, and, by now, I feel substantial need for data structures that can represent weighted graphs, both directed and undirected. Up till now, I was in a habit ...
2k views

### Traversing a stack in my DFS algorithm for finding a path in a maze

I am trying to get this code running as fast as possible when traversing through my stack of my DFS currently the input files are like so: ...
477 views

### Prim's MST implementation

This is my full working code. I am a bit confused about how I was able to use the structure MinHeapNode's variable in my Graph.cpp file. I used its ...
685 views

### A generic implementation of Dijkstra

Here is an implementation of Dijkstra As an rags-to-riches version of this Object oriented approach to Dijkstra's algorithm ...
1k views

### Object oriented approach to Dijkstra's algorithm

I'm seeking a code review for the following C++ implementation of Dijkstra's algorithm. I'm trying emphasize code reusability and extensibility but performance is also potentially important. ...
712 views

### Prove that the graph is a valid tree in Python

I recently solved this leetcode problem: Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make ...
159 views

### Bob the (Graph) Builder

I'm starting a project in which I'll generate random graphs and use algorithms to solve them. The first necessary step is obviously to build a graph. My graph has the following characteristics : ...