42

Data Structure Your terminology is a bit off. Trees have roots and children. Arbitrary graphs, on the other hand… I think "origin" and "neighbors" would be more appropriate. Visited flag: Storing the visited/unvisited flag in the Node hurts flexibility. Once you perform a dfs() or bfs(), that graph is "ruined". You won't be able to reset all nodes to ...


39

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 function does not actually determine if a graph contains a cycle. It determines if the graph contains a cycle starting at a given vertex. To detect a cycle, it ...


13

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 have strong evidence suggesting that readability is critical to making code easier to understand and therefore maintain. One of the critical factors in ...


11

Things you did well You defined i within your for loops, and abided by the C99 standards. You used an external library instead of writing your (more likely inefficient) own methods, and thus avoided unnecessarily reinventing-the-wheel. Things you could improve on: Efficiency: Copying a whole number into a external array with gmp_sprintf() in your ...


11

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: graph = {'A': set(['B', 'C']), 'B': set(['A', 'D', 'E']), 'C': set(['A', 'F']), 'D': set(['B']), 'E': set(['B', 'F']), 'F': set(['C', 'E'])} def dfs(graph, ...


11

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 it is making a copy of the edge list on every call (and recursive call). I ran your program against a maximum sized input, but it didn't finish in several minutes (I gave up). But when I ...


10

Couple of major issues. You are writing your own hash function. In addition some big problems. You are implementing your own hash based dictionary (badly). You need to use the visitor pattern (rather than have a mark in each node). The hash function: int Graph::getHashVal(std::string name) { int HashVal = 0; for (int i = 0; i < name.size(); i+...


8

The implementation of the BFS and DFS algorithms themselves seems correct(but it is a good practice to write unit-tests to make sure that it works as intended, so you should do it). However, your code in general is not correct. It definitely leaks memory: In the constructor, Adj is allocated: Adj = new vector<int>[V];. However, it is never deleted. ...


8

Iterables Generally speaking, if you use range(len(some_iterable))and then access an index of the item, you can just iterate over the item itself: for i in range(len(word)): # okay print(word[i]) for character in word: # better print(character) In your case it'd be key[:-1] Style Good on you for following PEP8. The code looks beautiful. There ...


7

As I mentioned in my other answer, hard-coding System.out.println() as the action for each node hurts code reusability. To let the caller specify the action to be performed on each node, without unrolling the recursion in the depth-first iterator, you can use the visitor pattern. import java.util.*; public class Graph<T> { public static ...


7

I don't need to mark the nodes as visited, when I traverse binary tree, right? Well, is your code working even though you are not doing this right now? Then yes, you don't need it. See also this question for a theoretical discussion about marking nodes as visited, and this question for a practical reason to mark nodes (it's not needed for a simple search, ...


7

There is at least one place where you may have problems with raw pointers. It has to do with exception safety and the piece of code I am talking about is the method addVertex (but it also applies to addAndGetVertex): void Graph::addVertex(int data) { Vertex* node = new Vertex(); node->data = data; node->edgeList.clear(); VerticesList::...


7

This code is pretty much the most efficient it can be, so I will add some pointers on the coding style and convention. Instead of calling your Binary Search Tree class a BST, define it as class BinarySearchTree(object): # remainder of your code Gives more meaning to the class name. The preorder traversal is called like t.preorder(t.root). But wait, t ...


7

I'll just work through this from the top: #include <stdio.h> #include <stdlib.h> #include <string.h> Looks good; we need these. typedef struct node_s { int *array; int size; struct node_s *next; } node_t; It's usual to use the same structure tag as the typename we're going to use: struct node_t. If size is the number of ...


6

Let's take a step back and consider the API. Suppose I want to test the BFS traversal on different graphs. To call GraphTraverseBFS I need to first create a BFS object. But the BFS constructor creates its own graph and runs GraphTraverseBFS on that. There is no clean way for me to just test it on my own graph. So let's say that's fixed. Now I want to ...


6

I think it would be fairly faster to store which numbers have already been used in two int[9] arrays and in one int[3][3] matrix. Then using bitmaps to represent which number have been used in each column, row and group. For example, when you put 3 in the cell (3,4), you would: row[3] |= 1<<3. column[4] |= 1<<3, group[1][2] |= 1<<3 and ...


6

I won't go into detail about memory management now, but it seems to be correct. You are deleting the edges and vertexes in the destructors, so you should't have any leaks. Things you could improve in the code: No need to define an empty constructor. Don't provide one if you have no manual initialization to perform. You don't have to typedef struct in C++, ...


6

Few things need explanation and correction. what is 53 in Graph::Graph()? getHashVal return value depends on the graph size, which may change as new vertices are added, so the same string may return different hash depending on the graph state. Is it intentional? Is there a way to clear visited attribute? If not, it is not possible to make another traversal. ...


6

Preliminaries It's conventional to include system headers with brackets instead of quotes and prefer std::vector over std::list unless proven wrong by a benchmark (note that the use of the word "list" in CLRS is not used in the same sense as std::list). #include <vector> #include <limits> Data structures Separate your algorithms and data ...


6

Firstly, use PyPy. $ python2 p.py Total: 29.8 seconds $ pypy p.py Total: 5.1 seconds PyPy actually does inlining, so the timeit overhead makes up a big part of that. Removing it gives $ pypy p.py Total: 4.1 seconds That's a factor-of-7 improvement already. Often PyPy 3 is faster, so to try that. To do you should change the prints to functions and use ...


6

If recursion has reached a leaf node then either you have accumulated the correct sum or not, but in no case it is necessary to check the left or right child node. Therefore I would change the first implementation slightly to public static boolean hasPathSum1 (Node root, int sum) { if (root == null) { return ...


6

Style I understand that this is a quick and dirty piece of code to earn some points on some code-challenge website. I will still offer some comments on style. private int v; This variable is never used outside of the constructor, in fact it is almost always shadowed by a method parameter. As such I would remove this member and the accessor getv() which ...


6

OOPs int maze_size[2]; int start_axis; int start_side; std::vector< std::vector< int > > dfs_path; Global variables should be avoided, as they can easily conflict with variables added in other places and don't allow easy duplication. And they're easy to avoid in an object-oriented C++ program (OOP). class Maze_Path { int maze_size[2];...


5

private static ArrayList<Node> nodeStore = new ArrayList<Node>(); // Stores all Nodes It's more common to put comments before the code. However, in this case, the comment is redundant. Either expand it to be more descriptive or remove it. private static List<Node> nodeStore = new ArrayList<>(); If you are using Java 8, ...


5

I see some things that may help you improve your program, but first let me thank you for asking a good question with a complete sample program. It makes things much easier to review and provides context for what you intend to do with your program. Use const where practical The current Graph<>::printAdj() routine does not (and should not) modify the ...


5

1. Review Code is easier to test (and measure the performance) if it's organized into functions or classes. In this case you have persistent data (W, H, grid, legal, start_pos) that's shared between the various parts of the code, so a class would be the best way to go here. It would be simpler to write: EMPTY_SPACE_SYMBOLS = '.' STARTING_POINT_SYMBOLS = '...


5

To use only static methods increases complexity of your code (because you need more parameters for function calls). In this review I won't change this to do not go to far away from your original code but you should also give it a try (for more complex code you will see a huge difference.) First of all let's move algorithm to a separate class: static class ...


5

Why take ownership of the graph? Since this is an operation on a graph, it seems to me it would be better suited to operating on a const reference of a graph, rather than taking ownership of the graph or a copy of it. Why is this a class? I see no reason why this couldn't be a free-floating function. Memoizer does not memoize Your memoizer does not ...


5

this code looks quite good already, especially if you integrate the tips of the other answer return value One problem I see though is that if you want to use your tree for something else than printing, it's not possible. This can be easily fixed by making the searches into iterators, and then print the elements def inorder(self, node=None): """traversal ...


5

I subscribe to everything @TobySpeight said. I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules: When in doubt, choose the simplest algorithm Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means ...


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