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

574 questions
Filter by
Sorted by
Tagged with
53 views

### Generate another random path through a complete graph

What this does is generate a random path of cities to later calculate the length of the newly generated tour of cities, the TSP. I am trying to figure out if there is a more efficient way to write ...
163 views

I would like to create a graph library for fun and run various searching algorithms on it. For now, all I have is an adjacency list that I threw together. The adjacency list currently only supports ...
196 views

### Kruskal Algorithm in C++

After studying from CLSR, I have implemented this algorithm. It prints the minimum cost. Help me to improve it. ...
86 views

### Computing most-cost effective loans in financial graphs using Java

Problem statement We are given a directed graph $G = (V, A)$, where $V$ is the set of actors and $A \subseteq V^2$ is the set of directed arcs. Existence of an arc $(u, v) \in A$ is ...
529 views

### Dijkstra's Algorithm implementation in C++

After applying suggestions from here about Bellman Ford Algorithm. Help me to improve this program. ...
2k views

### Bellman Ford algorithm implementation

Please review my code and help me to improve it. ...
471 views

### Eulerian Circuit algorithm

This method draws an Eulerian Circuit from a directed graph. The graph is represented by an array of Deques representing outgoing edges. It does not have to be Deques if there is a more efficient data ...
282 views

### Speed up a simple edge connecting algorithm

I have a list of edges and a similar list of links (linking edges) telling which edges to connect (how to order them). Connected edges form polygons and there can be many disconnected polygons (...
2k views

### Finding an Eulerian cycle in a graph

Given a graph that has an Eulerian cycle, write a function which returns the cycle in tuple form. I came up with following solution for this problem and am stuck trying to make it faster. Do you have ...
764 views

### Depth First Search using Adjacency List

My aim to implement adjacency list correctly. After takin help from here, I have implemented it. I have tried to implement it here, but it was suggested that it is most likely adjacency matrix. Help ...
3k views

I want to improve this code using STL. Let me know if I should add any other function in this code. ...
521 views

### Dijkstra finding shortest path satisfying given constraints

The question is originated from Hackerrank. Suppose there are 1 to N stores in a city which are connected by bidirectional roads associated with traveling ...
561 views

### BFS to check if path from start node to end node exists

I'm trying to solve a problem from leetcode called Jump Game and it seems to be a pretty simple graph problem where we have to find if a path exists from a start node to an end node. I personally ...
230 views

### Given {origin, destination} objects, find all the paths from a place to another

I have an object like this: ...
5k views

### Directed Graph Implementation in Java

Here I've attached my java implementation of a directed graph. I've used a modified adjacency-list mechanic to utilize a map instead of a list for quicker lookup times. Looking for comments / ...
39 views

### Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...
169 views

### Finding many paths in a graph

I have a graph which we can think of is representing a network of train tracks. Each node is a station and each edge is a piece of track connecting two stations. Each station node may be connected by ...
510 views

### Read CSV and use bidirectional BFS to find the shortest connections between actors

I have a really huge file¹ with 17 million records in it. Here is a sample of the file: Actor Movie 1,2 2,2 3,1 4,3 2,3 ...
694 views

### DFS implementation

I implemented DFS using recursion in Go. When I dfs the graph, I am able to get the path of traversal. But I'm unsure what else could I add to this DFS in order to make the search better. Also, Is ...
847 views

### Finding the shortest path (between source and destination) with the least number of edges

I wrote a program which finds the shortest path between a source and a destination in a graph, so that the path will be to one with th least number of edges. In order to write it, I used Dijkstra's ...
298 views

### Bare bone implementation of Dijkstra

I am trying to implement Dijkstra without writing lot of code for the Graph class itself. I have implemented it from Wikipedia. However, I am not fond of the way I have handled the minimum distance ...
90 views

### Algorithm to find connected tiles (percolation)

I wrote a little program in JavaFX which displays a path of neighbouring open tiles going from top to bottom. It should simulate a percolation. The algorithm iterates through the whole grid (every ...
205 views

### Java Node class for a Graph

I'm using ArrayList<Nodes> to store adjacent nodes, and ArrayList<Integer> to store the corresponding weights of the ...
5k views

I have written this Breadth First Search program using Adjacency Matrix, taking help from Introduction to Algorithm(CLSR) and from Internet. I want to optimise this code. ...
118 views

### A nice “live” service locator to flatten the object graph

Here is a class that exists in the Framework\ namespace in the xofz.Core library. It is used as a dependency of other ...
158 views

### Ruby Connected Components in a Graph

I've written the following code to find the connected components of a graph in ruby, but it is quite slow since I don't use any sensible data structure for the disjoint sets, and hence find_set is ...
114 views

### Computing resilience of the network presented as an undirected graph in Python

The idea is to compute resilience of the network presented as an undirected graph in form {node: (set of its neighbors)} for each node in the graph}. The function ...
626 views

...
765 views

### Graph represented by adjacency list

I've started to learn about graphs and how to represent them in code. Here is my attempt of making an adjacency list for an undirected graph. I'm looking for suggestions on how to improve it and what ...
62 views

### Calculating the connectance of a matrix iteratively

I have a performance issue in R. I have a function that iterates over a dataframe for different levels of "site" and "method". The function samples 1:1000 interactions (rows), converts these to ...
75 views

### SPOJ Fast Matching challenge

I wrote a solution to the MATCHING challenge on SPOJ: FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, ...
407 views

### Comparing Dijkstra's SSSP algorithm against Bellman-Ford in Java

Single source shortest path In SSSP, we choose a node $s$ and we compute all the shortest path starting from $s$ towards all other nodes, thus computing a shortest path tree. Two most classical ...
124 views

### Hackerearth - Learning Graph

Problem: Monk goes to graph city to learn about graphs, and meets an undirected graph having $N$ nodes, where each node has a value $i$ such that $1 \le i \le N$. Each node of the ...
52 views

### Find spanning tree with maximum edges with the same weight

For my university assignment I need to come up with an algorithm to find a spanning tree with maximum number of edges with same weight. I received an algorithm suggestion in this Stack Overflow answer....
538 views

### Calculation of Hamming distance between two adjacency lists

I have written a Java program to calculate the Hamming distance between two adjacency lists. The program calculates the Hamming distance correctly, but it takes a very long time, especially when ...
473 views

### How to make this code of shortest Path Finder more maintainable,extendable and get better static code analysis result?

I have the below code for finding the shortest path between a source node and destination node in a BiDirectional graph.It is working alright. However, when I am running Static Code Analysis (VS2017), ...
456 views

### Sorting directed graph topological using Kahn's algorithm

For a course I'm doing I need to get up to speed with Java, but unfortunately only Java 1.6 - here is a topological sorting algorithm in said Java version, for practice reasons: ...
966 views

### Weighted union-find with path compression in Python 3

I implemented the Union-Find data structure and would love to receive some feedback about my code. I have just begun programming and welcome any feedback or constructive criticism which would improve ...
103 views

### Network of senders and receivers in C++

I am trying to create a Sender-Receiver Network. What do I mean under a Sender-Receiver Network. That means that there is some structure which consists of Nodes and connections between them which will ...
280 views

### Depth-first search of a graph in C# (HackerRank problem)

I'm trying to solve a problem from HackerRank. I got the correct algorithm, but it seems to be too inefficient. After checking the code with 10 given test cases, 3 cases are good and 7 return a ...
1k views

### Topological sort of a graph

Please refer following graph. Please review following code for topological sort. I can sense one odd thing in my code, TS() is calling ...
2k views

### Prim's Algorithm using heapq module in python

Implementing Prim's with a $O(m\log n)$ run time using heaps, similar to Dijkstra heap implementation. Where $n$ is the number of nodes, and $m$ is the number of edges. Using the ...
1k views

### Greedy graph coloring

For taking part in a course, I need to learn some Java. Unfortunately they only teach Java 1.6, so I understand that later versions could simplify the below code a lot, but I have to stick with 1.6 ...
589 views

### Given two words and a dictionary's word list, find all shortest transformation sequence

This is a leetcode problem (https://leetcode.com/problems/word-ladder-ii/description/) Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(...
5k views

### Finding connected components in Python

I wrote an algorithm for finding the connected components in a 2d-matrix in Python 2.x. I am looking for comments on the quality of my code, organization, formatting/following conventions, etc. For ...
2k views

### Topological sort using STL

I am trying to implement topological sort using STL. I have used vector of lists to store adjacency list. Indegree is an array which stores indegree of vertices. ...
162 views

### Depth-first Search Non-Reursive Implementation in Clojure

I've created a non-recursive dfs implementation in Clojure. I'm using the wikipedia article on dfs as a guide. I'm very new to Clojure and functional programming in general. Any tips to improve ...
164 views

### AIO programming challenge - Friendlist - Who has the most friends?

I attempted this sample question from the Australia Infomatics Competition. TL;DR - Each line of input contains two numbers, representing a mutual friendship relationship. The output needs to be the ...