Hot answers tagged

49 votes
Accepted

Check if a directed graph contains a cycle

1. Review There's no docstring. What does the function do? What arguments should I pass? What does it return? This is the kind of function that would make an ideal candidate for a doctest or two. The ...
user avatar
  • 49.2k
37 votes
Accepted

BFS Implementation in Python 3

sets perform containing checks (w in visited) \$O(1)\$ rather than \$O(n)\$ for lists. ...
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 ...
user avatar
  • 49.2k
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 ...
user avatar
  • 49.2k
15 votes
Accepted

Dijkstra's algorithm in Python

(I'm assuming the code will be changed according to the comments. Otherwise it won't run with the given example graph) Performance issues: Comparing lists as in ...
user avatar
  • 10.3k
14 votes
Accepted

Finding all paths from a given graph

1. Introduction Your goal (if I understand correctly, of generating all the execution paths in a state transition graph for a Java thread and then using those execution paths to test the code) seems ...
user avatar
  • 49.2k
14 votes
Accepted

Depth-first search in Python

DFS should keep track of all the nodes visited. Not the node. The node only properties is it self, and it's children. Check this amazing implementation: ...
user avatar
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: ...
user avatar
  • 1,312
13 votes

Kosaraju in Scala

The first thing that I see is a fundamental issue that would be a problem regardless of the programming language used - long procedures. The folks who study the human aspects of software development ...
user avatar
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. ...
user avatar
  • 28.4k
12 votes
Accepted

My attempt at Dijkstra's Algorithm in Python 3

Those comments are very difficult to read. ...
user avatar
  • 9,553
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 ...
user avatar
  • 28.4k
11 votes
Accepted

Implementing graph search

There are some things that you could do to improve your code: First of all, your functions clearly lack documentation. Unless you know a little bit about graph theory, it is quite hard to guess that <...
user avatar
  • 19.9k
11 votes
Accepted

Trip Advisor - Train routes

First of all, you have a possible bug in your code. If trains is empty you will get a problem at the printing of the results. Don't code that much inside the ...
user avatar
  • 50k
11 votes
Accepted

Cycles of pointers

I'm not convinced that what you are doing really makes sense, but I did see the recursive pattern in your code and I believe that this is how you can refactor it. First of all, we create a method ...
user avatar
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 ...
user avatar
  • 49.2k
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 ...
user avatar
  • 19.1k
10 votes

Trip Advisor - Train routes

Constructor You seem to have everything in your constructor. This isn't really great practice. You use your constructor to initialize all of your variables, so you'd have something like: ...
user avatar
  • 2,216
10 votes

Word Morph (changing one letter at a time)

if ancestor == None: The part == None is unnecessary and adds noise to your code. Since ...
user avatar
  • 13.2k
10 votes
Accepted

Ford-Fulkerson Algorithm: Max flow

Input Parsing. You declare a Scanner to process your input, but then you don't use it very effectively. Your code: ...
user avatar
  • 96.8k
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, ...
user avatar
  • 3,589
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 ...
user avatar
  • 7,673
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 ...
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 ...
user avatar
  • 191
9 votes

Milking order compatible with maximum number of observations

...
user avatar
9 votes
Accepted

Graph puzzle resolver

...
user avatar
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 ...
user avatar
  • 3,449
8 votes

Trip Advisor - Train routes

The purpose of a constructor is to create an object. What is the purpose of a TripAdvisor object here? It seems it has no purpose as an object. You "create" a ...
user avatar
  • 108k
8 votes
Accepted

Depth First Search and Breadth First Search in C++

The implementation of the BFS and DFS algorithms themselves seems correct(but it is a good practice to write unit-tests to make ...
user avatar
  • 5,550
8 votes
Accepted

Shortest path using Breadth First Search

There are several places in this code where a loop is redundant(or at least can be simplified). For instance, this for loop: ...
user avatar
  • 5,550

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