37
votes
Accepted
BFS Implementation in Python 3
sets perform containing checks (w in visited) \$O(1)\$ rather than \$O(n)\$ for lists.
...
- 28.6k
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 ...
- 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 ...
- 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:
...
- 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.
...
- 28.5k
12
votes
Accepted
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 ...
- 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 ...
- 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 ...
- 19.3k
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:
...
- 97.3k
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, ...
- 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 ...
- 7,764
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 ...
- 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 ...
- 191
9
votes
9
votes
Accepted
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 ...
- 3,579
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 ...
- 3,736
8
votes
Maze solver for 2D matrix in Ruby
I think your code shows ability of writing readable code, understanding and implementing algorithms, writing helpful comments, and if the code works like I believe it does, providing a working ...
- 197
8
votes
Accepted
"Researcher Hatim is right or wrong" challenge
You don't need a class
I highly recommend the Stop Writing Classes presentation. The typical situation it describes : a class with two methods, an init and a run is exactly what you've done.
...
- 29.2k
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 ...
- 21.6k
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 ...
- 94.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 ...
- 11.6k
7
votes
Implementation of Prim's algorithm in C++
Code looks OK.
I would suggest you to do some class instead of Edge:
...
- 1,480
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 ...
- 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 ...
- 23.5k
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 ...
- 42.7k
7
votes
Accepted
Undirected graph implementation
public class Graph
Is there any reason not to make it Graph<TVertex>?
...
- 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 ...
- 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)
...
- 27k
Only top scored, non community-wiki answers of a minimum length are eligible