# 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.

588 questions
Filter by
Sorted by
Tagged with
717 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 : ...
1k views

### Graph as adjacency lists: BFS DFS Topological Sort

I have written some code to practise graphs. Graph is represented as vector<list<int>> . Would you share some feedback with me? Are algorithms correct ...
932 views

### All your bases are belong to Dijkstra

CATS, willing to get a hold of all the bases, asked Dijkstra to give him a hand designing the most powerful algorithm to reach all bases with the least distance travelled. I tried to implement the ...
915 views

### Graph theory using C++ STL

I'm trying to practice STL so I implemented breadth first search and depth first search. I have designed the graph class so that vertices can be arbitrary hashable object. Any feedback would be ...
2k views

### Simple Oriented Graph implementation in Java

I wanted to implement a simple oriented graph as part of an exercise in both Object Oriented Programming and Data Structures. I wanted to make it as class-focused as possible, so I don't know if my ...
4k views

### C++ Graph Implementation

My data set is a list of Edges which are passed as a pair of integers. Based on that, I have the following graph implementation for BFS. Could someone please review ...
152 views

### Vertex cover approximation in JavaScript

I believe this runs in $O(V+E)$ but I wouldn't be able to explain the reasons why. I was looking for some general code review and any help on understanding the runtime. ...
229 views

### Return the Euler Cycle for a graph with es6

My algorithm for finding an Euler tour of a digraph, G⃗, if such a tour exists, starting from some vertex, v. ...
2k views

### Finding a loop in a directed graph in Python

I wrote this code to find if a directed graph contains a loop or not. I am pretty new to graphs and I saw some examples on the internet but couldn't actually understand their implementations. So I ...
3k views

### Depth first search implementation

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the depth first search section (5.8) using javascript. Note you can execute the code here if you don't ...
191 views

### Graph radius in Java - follow-up

See the previous and initial iteration. Terminology Given an undirected graph $G = (V, E)$, the eccentricity of a node $u \in V$, $e(u)$, is the maximum length (number of edges) of a shortest ...
3k views

### Breadth first search implementation (also includes functions for finding shortest path and number of connected components)

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the breadth first search section (5.7) using javascript. I also have a ...
735 views

(See the next iteration.) The following snippet is a brute-force algorithm for computing a graph radius in time $\Theta(V^2 + VE)$ and space $\Theta(V)$ simply by doing $|V|$ breadth-first ...
866 views

### Graph Interface: Storing Vertices in an Array vs HashTable

I have just started learning graph algorithms and am trying to arrive at an ideal interface. I understand that this code will not be used anywhere else (I will certainly use Boost::Graph) but I just ...
1k views

### Random Contraction Min Cut (Karger) - performance issues

(Offtopic note: I can't add a "networkx" tag.) I reworked an old algorithm, this time not implementing the graph on my own, but building on the networkx module. Script works fine for the tests and ...
73 views

### Finding all backedges in an undirected graph

I have tried to implement the DFS algorithm to find all the back-edges in a graph that lead to a cycle in the graph: ...
1k views

### BFS for modified shortest path

Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ? The itinerary of ...
3k views

### Converting a List of arcs into Adjacency list representation for graph using dictionary

I was reading up on implementing Graphs in Python and I came across this Essay at python.org about graphs, so I decided to implement it, but with weighted edges. I start with arcs and their cost ...
617 views

### Shortest path from U to V using at most k nodes

I'm trying to solve a problem that asks for a shortest path between two cities with at most k nodes. The first line of input has the number of test cases. On the second line 3 integers are given, ...
735 views

### Speeding up Python depth-first search in large graph

I'm building a Markov text poetry generator. The main method, which is attached below, performs a depth-first search through the Markov chain, which is implemented as a NetworkX digraph of Word ...
84 views

### Kruskal's algorithm

I'm working through Coffeescript implementing simple algorithms (started with Prim's as reviewed in this previous post) and wrote out Kruskal's algorithm as below, with a few helper functions. I'd ...
2k views

### Directed graph isomorphism in Java

Given two input directed graphs $G_1 = (V_1, A_1)$ and $G_2 = (V_2, A_2)$, the problem of isomorphism asks whether the two directed graphs are isomorphic, or in other words, whether the two input ...
89 views

### Prim's algorithm in CoffeeScript

I'm just starting to learn CoffeeScript and am trying to work through simple examples, this one being Prim's algorithm. I'd like feedback on everything but especially on making this script take ...
38 views

### Find order to install dependencies

Given a JavaScript map object of dependencies and their dependencies, determine order to install them: Example: Input: ...
3k views

### Ford-Fulkerson Algorithm: Max flow

I have worked on the Ford-Fulkerson algorithm and have following code. The code works fine, but I fill I could do more code optimization, I have worked on it for few days. Question: Is there any ...
2k views

### Brute force shortest path in Java

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
401 views

### Creating a time-course dependent, correlation-based directed graph with Networkx

I have a correlation matrix containing 4 time points, each with multiple samples. Each sample is identified with a time point with its name. What I am trying to accomplish here is to create a directed ...
333 views

### TrieMap based Simple Graph API

Looking for some feedback regarding elegance, about my code below implementing a simple graph API basing on scala.collection.concurrent.TrieMap. Background: I am ...
1k views

### Maze solver for 2D matrix in Ruby

I got rejected for a junior Ruby job entry where I had to solve a 2D matrix as a maze with walls. This is the main class: solver.rb ...
67 views

2k views

### Java DFS Implementation that tracks time and parent node

I have a project where I'm to implement a DFS using a direct graph. The implementation should print the currently visited vertex, the parent (the node from which the current node was reached), and the ...