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.

Filter by
Sorted by
Tagged with
4
votes
1answer
87 views

Sort and describe itinerary segments

Given some incoming some data in JSON format, representing unsorted train, bus, and flight tickets: ...
3
votes
2answers
8k views

Java: Given a list of edges, build a tree and return the root

In an interview I was asked to write Java code to build a tree and return the root, given a list of edges. It was a fairly open ended question where the interviewer left all the decisions up to me. I ...
2
votes
1answer
7k views

Adjacency List implementation for Graph in Java

I am building up a Graph repository which I am planing to use for exploring all the Graph algorithms. This is more from a learning perspective only. I have implemented a basic ...
3
votes
2answers
128 views

Computing most reliable path in undirected probabilistic graphs using Java

(See the next iteration.) Problem definition We are given an undirected graph \$G = (V, E)\$ and a weight function \$w \colon E \to (0, 1]\$. The weight of the edge \$e \in E\$, \$w(e)\$, ...
1
vote
0answers
116 views

Calculating distances between nodes in graph with negative cycles

Full disclosure: this is for an online course. The code calculates the distances between a starting node in a graph and all other nodes using the Bellman-Ford algorithm. The graph may contain ...
2
votes
1answer
243 views

Most efficient implementation of Djisktra's shortest path using vectors and pairs in C++ stl

If std::vector<vector<pair<int,int> > > v(n) represents the adjacency list of the graph with ...
3
votes
1answer
405 views

CodeFights Quora bot

This isn't any homework questions or assignments, only my practice. In the CodeFights Quora bot. My code cannot pass even the first hidden input because of the execution time. I'm only a first-month ...
2
votes
0answers
133 views

Neo4j traversal algorithm to find dense nodes

I am trying to get familiar with traversals algorithms implementations in Neo4j and to practice I am implementing classic graph algorithms (not judging if is the best approach or not, just for the ...
3
votes
1answer
3k views

Undirected Unweighted Graph Implementation - C++

For a class we needed to implement an undirected unweighted graph that: Maintains a distance matrix that can be printed Supports the computation of the graph's diameter (uses dist matrix) Prints the ...
2
votes
1answer
3k views

Finding minimal spanning tree of a graph using Kruskal's algorithm

I am doing some practice interview questions for class, one of the questions is: Given an undirected graph G, find the minimum spanning tree. Function should take in and output an adjacency list. ...
3
votes
1answer
336 views

Lissajous pattern simulator

I had seen a YouTube video making actual Lissajous patterns with sand falling from a pendulum with 2 different periods and looking in the Wikipedia page the looked very easy to simulate. I made a ...
1
vote
1answer
6k views

MST Kruskal's algorithm in Python

I have this code for finding MST for undirected weighted graph, currently works for graphs with maximum 10 vertices. How can I update the code to scale for larger graphs? ...
4
votes
2answers
2k views

Depth and breadth first search

I am practicing interview questions, I wrote this code to perform BFS and DFS on a graph in Python. How can it be optimized, and how can it be made more readable? ...
4
votes
1answer
2k views

Undirected graph implementation

I have implemented in C# a graph data structure (undirected graph) using TDD technique, tests are provided upfront. This implementation provides common graph methods also it traverses graph using DFS ...
1
vote
3answers
1k views

Dijkstra implementation for maze solving that works fine and returns shortest path

I would like to make my code "prettier" and also speed up the runtime of my implementation. Nodeinfo is literally just an object that holds its "parent node"(the node it came from) and its distance. i ...
5
votes
1answer
1k views

Karger's min cut algorithm

I have implemented a simple version of Karger's min cut algorithm. The algorithm takes a graph and repeatedly contracts randomly selected edges until only two nodes are left. By repeating this ...
8
votes
1answer
1k views

Flight combinations between two cities

I am trying to obtain all possible ways to go from a city A to a city B on a given day by plane, with a maximum of 2 stops. I have as input a list of dictionaries: ...
6
votes
0answers
358 views

Kattis problem Amanda Lounges

I wrote this solution to Kattis problem Amanda Lounges in Scala. TL;DR: It's a graph theory problem where I read in a list of edges from stdin and try to compute the minimum number of nodes that ...
9
votes
1answer
2k views

Hacker Rank: Journey to the Moon (Graph Theory)

I am attempting to complete the "Journey to the Moon" problem described below: There are N trained astronauts numbered from 0 to N-1. But those in charge of the mission did not receive ...
1
vote
2answers
170 views

Java sequential BFS

I am currently working on optimizing my code. In order to do that, I have to make sure that my sequential BFS works perfectly. Then, I should I apply threads or executor service to run it in parallel. ...
6
votes
2answers
186 views

Is there a circular reference in a set of template substitutions?

I have a configuration engine that allows the user to specify a dictionary with text templates (read from a JSON file) where each placeholder like {x} can be ...
3
votes
2answers
2k views

Dijkstra's algorithm in JavaScript

I'm trying to implement Dijkstra's algorithm to find the shortest path. This is from a challenge on CodeWars. In this scenario there is a map: ...
6
votes
2answers
543 views

Simple Graph in Python

Just the beginning of graphs API in Python: ...
9
votes
2answers
330 views

Rock, Paper, Whatever - A small commandline game

My rational for this program, was to learn more of Python's standard library, I didn't actually know cmd was even in it until I started this program. It's also the ...
4
votes
2answers
363 views

Split DAG into disjoint sets

I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding ...
2
votes
1answer
98 views

Circle check algorithm optimization for directed graph

Here is my two versions of code to check if there is a circle for a directed graph. Any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are highly ...
1
vote
1answer
207 views

Leetcode 210. Course Schedule II

Problem statement There are a total of \$n\$ courses you have to take, labeled from \$0\$ to \$n - 1\$. Some courses may have prerequisites, for example to take course \$0\$ you have to ...
2
votes
0answers
43 views

Modeling a control polygon for a piecewise spline curve

Aim I'm modeling a control polygon for a piecewise spline curve. Each sub-spline is defined by a location the spline must pass through, as well as a forward tangent, and a backwards tangent. The ...
2
votes
1answer
1k views

Representing an adjacency list (graph) using a hash table of lists

While writing a C++ implementation for weighed, labeled graphs, I started to doubt the effectiveness/correctness of my chosen structure and I would like to hear some reviews. I tried to implement the ...
0
votes
2answers
380 views

BFS in a grid with wall breaking saldo in Java

In this problem, we are given a 2-dimentional grid, with each cell being walkable or holding a wall. Given an integer \$s \geq 0\$, find the shortest path from the source node to target node breaking ...
2
votes
0answers
406 views

Second degree connection ranking

Problem Find 2nd degree connections ( friends’ friends), output these 2nd degree connections ranked by number of common friends (i.e 1st degree connections) with you, (example: if 2nd degree ...
6
votes
1answer
278 views

Minimum number of flight segments using breadth-first search

I'm practising with graphs, and trying to solve a problem of calculating the minimum number of flight segments, applying breadth-first search. The code is working, but I think, that it's not clean. ...
8
votes
2answers
2k views

Hackerrank - value of friendship (II)

Problem statement You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no ...
3
votes
1answer
1k views

Eulerian Path algorithm

I'm doing a project to find the Eulerian path. Cane someone find an example where the algorithm is wrong? The function EulerianPath recursively prints the Eulerian ...
5
votes
1answer
1k views

Hackerank - value of friendship

Problem statement You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no ...
2
votes
0answers
422 views

Tarjan's strongly connected component finding algorithm

Here is my code for Tarjan's strongly connected component algorithm. Please point out any bugs, performance/space (algorithm time/space complexity) optimization or code style issues. ...
5
votes
2answers
1k views

Implementation of a graph in Java

A long time ago I posted my implementation of directed graph is Java. Recently I took a look at @coderodde's implementation and decided to write an implementation of undirected graph and directed ...
2
votes
0answers
183 views

unordered_multimap approach to adjacency list and graph search

I'm looking for suggestions on how to improve the usage of modern C++ features with this simple graph search algorithm, particularly with regard to the use of STL containers and lambda expressions. ...
4
votes
3answers
2k views

Dijkstra's algorithm using priority queue running slower than without PQ

I need to implement dijkstra's algorithm and I've done so using this Wikipedia page. I've done it both with priority queue and without. Both versions work 100% correct, however I need the faster one ...
4
votes
1answer
171 views

Code to calculate minimum number of pushes required to put the whole dominoes set down

The question is this one on UVa, and it basically gives us n, the number of dominoes and (a,b) relations such that pushing ...
4
votes
2answers
501 views

Dijkstra's algorithm using a specific structure

I have implemented Dijkstra's algorithm using a slightly modified version of the structure and class posted here. Unfortunately, I have ruined the efficiency. I am intent on using this structure. I ...
3
votes
3answers
612 views

Graph representation implementation

I wanted to represent graphs in Python, and wrote the following class. I don't care about values associated with nodes or the weights of the connections between them, simply the connections between ...
3
votes
1answer
3k views

BFS' shortest path unweighted directed graph

The code I have is based on BFS and a little bit of Dijkstra and returns the shortest path of an unweighted directed graph as an integer. I was wondering if someone could take a look at my code too ...
3
votes
1answer
114 views

Topologial Sort in Python

I am trying to self study algorithms and this is my attempt at topological sort using Tarjan's version of DFS. It runs correctly for the graph I included. Can someone tell me if this is correct and if/...
6
votes
1answer
4k views

Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class ...
3
votes
2answers
710 views

CLRS Implementation of BFS and DFS in C++

I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code? GraphStructures.h ...
1
vote
1answer
850 views

Tarjan's strongly connected components algorithm

Can anyone suggest to me how I can make this "nicer"? If you can see any glaring details that I could change to speed things up too, that would be great -- though it's not priority. ...
4
votes
1answer
370 views

Snakes and Ladders using a magic die

This is a problem from here where you're given a magic die, and the objective is to find the minimum number of dice throws (hops) to go from the start point to the end of the board, and win the game. ...
4
votes
1answer
1k views

Implementation of BFS on a graph

I have written the code below as a BFS implementation. Could someone please review. In particular, I want to know if there could be a memory leak. ...
0
votes
2answers
246 views

Adjacency list from scratch

Here is my code for implementing an adjacency list from scratch. I would like to get feedback from the experts for optimization. ...