Skip to main content
37 votes
Accepted

BFS Implementation in Python 3

sets perform containing checks (w in visited) \$O(1)\$ rather than \$O(n)\$ for lists. ...
301_Moved_Permanently's user avatar
21 votes
Accepted

Adjacency List Graph representation on python

Here are two ways you could represent a graph with weighted edges in Python: Represent a graph as a mapping from a node \$n\$ to a mapping from neighbouring node \$m\$ to the weight \$w\$ of the edge ...
Gareth Rees's user avatar
  • 49.6k
18 votes

Milking order compatible with maximum number of observations

1. Review Python's style guide recommends 4 spaces for each level of indentation, and keeping lines to a maximum of 79 characters. It's not compulsory to follow this style, but it makes it easier for ...
Gareth Rees's user avatar
  • 49.6k
14 votes

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

It looks like you found a pretty nice approach there already. A few general things stand out: Using globals Magical constants and unsafe C-style arrays/raw pointers: ...
sehe's user avatar
  • 1,322
12 votes
Accepted

Sum of all paths between all pairs of nodes in a tree

\$O(n^2)\$ time complexity Your current algorithm has \$O(n^2)\$ time complexity because for each edge, you count the number of vertices on one side of the edge, which is a linear time operation. ...
JS1's user avatar
  • 28.5k
12 votes
Accepted

My attempt at Dijkstra's Algorithm in Python 3

Those comments are very difficult to read. ...
Veedrac's user avatar
  • 9,613
12 votes
Accepted

Hacker Rank: Journey to the Moon (Graph Theory)

The big problem The reason your program runs so slowly is that your dfs() function takes the edge list as a parameter by value instead of by reference. That means ...
JS1's user avatar
  • 28.5k
11 votes
Accepted

Social network broadcast message algorithm

1. Bug The algorithm does not always find the minimum number of messages! Suppose that we have the following follower graph (an arrow from A to B means that A follows B). To reach everyone, only one ...
Gareth Rees's user avatar
  • 49.6k
11 votes

Graph coloring project in C++

That's a lot of code. Consider just using STL? ;) Seriously, though, you wrote an entire List utility class, almost 500 lines of code, and: It doesn't work ...
Quuxplusone's user avatar
  • 19.4k
10 votes
Accepted

Generic graph implementation in C#

Vertex The separate properties and backing store are redundant. We don't do anything extra when getting or setting the values so we can just use the properties. When we have multiple constructors, ...
AlanT's user avatar
  • 3,599
10 votes
Accepted

Rainfall - August 2016 Community Challenge (Hooray for graphs!)

NetworkX is nice, but you really aren't using a lot of its features, and the features you are using end up not being that pivotal; your implementation won't be changed (much) if you remove NetworkX ...
Dan Oberlam's user avatar
  • 7,814
10 votes
Accepted

Create a build order from a list of projects and their respective prerequisites

Algorithm Correctness Due to a small problem in GetBranchPrecedents this algorithm does not actually work. The case that all parents might already be present in the ...
M.Doerner's user avatar
  • 1,500
9 votes

BFS Implementation in Python 3

I agree with Mathias Ettinger's use of sets and deques, with two changes: name the set seen ...
sesotek's user avatar
  • 191
9 votes

Milking order compatible with maximum number of observations

...
Peter Taylor's user avatar
  • 24.1k
9 votes
Accepted

Graph puzzle resolver

...
Peter Taylor's user avatar
  • 24.1k
9 votes

Graph coloring project in C++

A few notes to add to the existing answer(s): It is not wrong use not in place of ! but I'd like to claim that most programmers ...
Juho's user avatar
  • 3,589
9 votes
Accepted

Find all paths in a graph

I don't think memoization will be useful here. Any correct algorithm is going to be O(n!), nothing you do can reduce that fundamentally because you still have to output all the paths. Trying to cache ...
ShapeOfMatter's user avatar
8 votes
Accepted

Dijkstra's algorithm in Rust

Pay attention to compiler warnings. Rust is a statically-compiled language. One of the big reasons you choose such a language is to get information at compile time: ...
Shepmaster's user avatar
  • 8,658
8 votes
Accepted

Sort a list of pairs representing an acyclic, partial automorphism

Code style Use constants for variables that do not change. Eg const sortedArray = []; Don't include the type in the name, Eg ...
Blindman67's user avatar
  • 22.1k
8 votes
Accepted

Graph implementation with Dijkstra

Graph seems quite reasonable: But your distance implementation is not an implementation of Dijkstra. Dijkstra finds only the cheapest path between two nodes (technically). But I suppose you can use ...
Loki Astari's user avatar
  • 95.3k
8 votes

Compute shortest path in undirected graph

Intro code: There's a lot of "instant fail"s here: Include only the headers you need! Debugging macros are probably not acceptable for something like this. We can step through in a ...
user673679's user avatar
  • 11.8k
8 votes
Accepted

Bug Byte puzzle from Jane Street

This submission would benefit from the addition of profiling measurements. mutable default This signature has well-defined semantics. But please don't do it. Human maintenance engineers in future will ...
J_H's user avatar
  • 29.1k
7 votes

Implementation of Prim's algorithm in C++

Code looks OK. I would suggest you to do some class instead of Edge: ...
Nick's user avatar
  • 1,582
7 votes

Generic graph implementation in C#

In addition to AlanT's great review: The IsVisited property is actually not a property of the graph, because it stores the state of the search. That state should ...
JanDotNet's user avatar
  • 8,538
7 votes
Accepted

Dijkstra's algorithm in C99

Generally the variable and function naming is clear and makes the code easier to read. If this program is for a first or second year computer science class it's really very good. If you are new to C ...
pacmaninbw's user avatar
  • 24k
7 votes
Accepted

Flight combinations between two cities

Your code's runtime is \$O(n^3)\$, this is almost definitely not the performance that you want. The simplest way to solve your problem is by, you guessed it, a graph. Take the following directed graph ...
Peilonrayz's user avatar
  • 43.4k
7 votes
Accepted

Undirected graph implementation

public class Graph Is there any reason not to make it Graph<TVertex>? ...
Peter Taylor's user avatar
  • 24.1k
7 votes
Accepted

Prim's Algorithm using heapq module in python

1. Review There is no docstring. What does prims do? What argument does it take? What does it return? The text in the post would be a good starting point for a ...
Gareth Rees's user avatar
  • 49.6k
7 votes
Accepted

Breadth First Search using adjacency list

Will be fixed soon Advice 1 In BFS, you don't really need colors. (See alternative implementation.) Advice 2 (Exposing internals) ...
coderodde's user avatar
  • 28.7k
7 votes
Accepted

Displaying programming languages on a timeline

First of all, congratulations, the result looks really good and that's a lot of work for an exercise! I particularly like how you frequently used standard algorithms. That is also quite a lot of code ...
papagaga's user avatar
  • 5,757

Only top scored, non community-wiki answers of a minimum length are eligible