Tag Info

46

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

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

15

What further improvements can I make to this code? The code is rather bad - the site you read it from tends to have lots of bad/amateur articles. The graph class: std::map<int, bool> visited; std::map<int, std::list<int>> adj; This is extremely poor and inefficient graph implementation. std::map creates a new memory allocation for each ...

13

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

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

12

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

12

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

10

Disagreement I have to disagree with @ALX23z blanket statement that using std::map is bad idea. There is a lot more to it than that (if the graph was sparse the map is great). But you don't give enough contect to evaluate the graph implementation. All I can say it is an acceptable "basic" implementation. Overall Things that are actually bad: 1: The ...

9

I've assumed here the OP is performing DFS on undirected graphs - if not only my second point is valid. There are several other answers here suggesting better coding practices and more efficient implementations, but they're missing the biggest problem with you code: it doesn't perform depth first search! To demonstrate this run it with the graph created by: ...

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

8

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

8

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

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

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

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

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 isn'...

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];...

6

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 = '...

6

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

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

This is a nice answer to a fun challenge. There are a couple ways I can see to improve it. This solution only works for arrays of up to 10 values due to the for loop terminating after 10 iterations. We can make it work for an arbitrary number of values by closeing the channel when Walk has complete, and testing for each channel's state to match. Testing ...

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