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
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
351 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
366 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
237 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
1k 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
718 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
377 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
163 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
148 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
457 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
544 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
2k 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
109 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
645 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
722 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. ...
3
votes
1answer
337 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
236 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. ...
2
votes
1answer
955 views

Get a path between graph nodes using breadth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using breadth-first search. I'm doing this to improve my style ...
1
vote
1answer
299 views

Return a path between graph nodes using depth-first search redo

I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this ...
2
votes
1answer
3k views

Return path between graph nodes using depth-first search

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. I'm doing this to improve my style ...
1
vote
1answer
447 views

Print Connected Components Scala

Given a file containing adjacent IDs: i1, i2, i5 i3, i4 i2, i6, i7 i4, i8 i9, i3 I would like to print each of the connected components: ...
4
votes
0answers
104 views

Graph Python challenge 2 (revised)

I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python: You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
2
votes
1answer
3k views

Implementation of a directed graph

I wrote an implementation of a directed graph using the adjacency list representation. My goal was to meet the big O requirements which I'd found here. Please let me know about any drawbacks of the ...
5
votes
0answers
150 views

Assembling and traversing a graph, given a list of items and parent pointers

I've written a function which takes input such as this: ...
4
votes
1answer
625 views

Finding the max cost from the minimum cost incurred on travelling

This problem is from INOI 2014 , where I have find out the maximum cost of traveling through the cities but taking the minimum possible route cost , here is an excerpt from it, Indian National ...
3
votes
1answer
300 views

Python graph challenge

I'm looking for ways to optimize a function that I wrote as an answer to this problem in Python: You and your rescued prisoners need to get out of this collapsing death trap - and fast! ...
2
votes
0answers
528 views

C++ STL graph implementation with out and in adjacency list

I'm looking for a code review on the following C++/STL graph implementation: Edge ...
1
vote
1answer
473 views

Convert a List of graph edges to a Map of neighboring nodes

What would be best way achieving this? Is it possible to use Immutable map? ...
0
votes
1answer
591 views

Node comparison using priority queue for Dijkstra's Shortest Path Algorithm

Instead of using a MinHeap that will allow me to change the vertex priorities I am using the Java library PriorityQueue. Here ...
1
vote
1answer
563 views

Directed Acyclic graph implementation in Ruby on Rails

I have an implementation for a graph node class that I'd like to have function as a directed acyclic graph. The associations are roughly as follows ...
2
votes
2answers
48 views

Longest way for all vertex

how can I optimalize this code? ...
4
votes
0answers
64 views

Finding connected components in the application task

I have n indexed socks, each of which has one of k colors. I also have a list that states which two socks I must wear at each of ...
1
vote
1answer
765 views

NBA*: Very efficient bidirectional heuristic search algorithm in Java - follow-up

This post elaborates on NBA*: Very efficient bidirectional heuristic search algorithm in Java. I have made the following changes: Added an explicit type for representing digraph paths: ...
0
votes
1answer
87 views

Social network broadcast message algorithm (part 2)

This is new code and continue discussion from thread (Social network broadcast message algorithm), and this thread focus on build new graph from strong connected graph part. Let me post the problem ...
0
votes
2answers
90 views

Code for number of routes possible of the given length between 2 given nodes

Recently I came across this problem , here is an excerpt of it, It is well known that the routing algorithm used on the Internet is highly non-optimal. A "hop", in Internet jargon, is a pair of ...
1
vote
1answer
674 views

NBA*: Very efficient bidirectional heuristic search algorithm in Java

(See also the next iteration.) I have implemented NBA* (New Bidirectional A*) in Java and compared it against conventional A* and Dijkstra algorithms. The results may be as optimistic as this: Seed =...
6
votes
2answers
2k views

Strongly connected component algorithm in Python 2.7

This is my implementation of Kosaraju's algorithm for detecting strongly connected components, post here for advice. Some special areas looking for advice, Not sure if my current implementation for ...
3
votes
1answer
4k views

A*, Uniform cost and Greedy Best first search implementations

I am writing the code for A*, Uniform cost search and Greedy best first search algorithms in Java. I have finished the code which is working fine but I have used a bit different design strategy while ...
2
votes
1answer
124 views

Internal method to calculate the distance between all nodes in Kruskal's Importance (Driver) Algorithm

I've been trying to reduce the indentation from a method in my code. The solution will probably be unrelated to the language, in this case python, although it may rely on some python specific ...
4
votes
1answer
2k views

Graph represented by an adjacency matrix in C++

I'm working on my data structures knowledge and wanted to create a graph with a small DFS driver which simply prints the nodes as it visits them. Here's my graph class: ...
4
votes
1answer
3k views

Dijkstra's algorithm using a dictionary for the priority queue

Unrelated to code: This is my first project in Python using classes and algorithms. I have spent the last week self teaching myself about queues and stacks, so I am NOT trying to use any Python ...
5
votes
1answer
85 views

Calculating how similar two objects are according to a database

I want to calculate how similar two objects are according to a database. However the code is very slow; it takes around 2 minutes to analyze just 3 objects. How can I speed it up? I have tried to ...
3
votes
1answer
4k views

Implementing an Adjacency List in C

I haven't yet implemented any sort of graph thus far in C and decided to give it a go by trying to implement an adjacency list in C. Is there anything in my code that you see that I can improve and is ...
5
votes
1answer
562 views

Social network broadcast message algorithm

Working on below problem and post problem and my current code. My idea is to always iterate from the minimal in-degree node which has not been visited before. Then based on this node to do a BFS. I am ...
1
vote
0answers
48 views

FindUnion data structure used to find the minimum cut of a graph

I am trying to find the bottleneck in my code for computing the minimum cut of a graph. Currently the program runs in about 40 minutes on the test data set linked below (200 nodes and ~2000 edges). I ...