# Tag Info

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

35

sets perform containing checks (w in visited) $O(1)$ rather than $O(n)$ for lists. collections.deque are better than lists for poping elements at the front (popleft). you should put your example code under an if __name__ == '__main__' clause. w as a variable name does not convey meaning, you should try to come up with something more explicit. import ...

14

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: static vector<uint64_t> *movie_map = new vector<uint64_t>[1200000]; static vector<uint64_t> *actor_movie_map = new vector<uint64_t>[2000000]; I'd suggest using std::...

11

As far as I can tell, this code seems pretty easy to follow, especially with the comments. Here are several things that stood out to me: Since you haven't provided your own queue implementation, I assume you're using std::queue. If so, remove using namespace std and use std:: where necessary. This entire method should be const. You're modifying three ...

10

Cosmetics At first glance, your post looks about right... until the Program class. But before I dig into the matter of the subject, I like to scratch the surface a bit. Whitespace Consistency Try to be more consistent with vertical whitespace. I think the Node and Program classes have it right: internal class Node { public string Name { get; private ...

9

Much of the code looks good. Some comments could be clearer, and there are some correctness issues. In is_leaf(), please strike this redundant remark: # Check if both left child and right child have no value The code makes perfect sense as it stands. Code should say what is specific, and comments should speak in generalities that wouldn't be obvious ...

9

Here's the code you want to speed up: // Checks if the 2 provided puzzles are the same bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2) { for ( int length = 0; length < PUZZLE_LENGTH; length++ ) if ( puz1.state[length] != puz2.state[length] ) return false; return true; } bool puzzleExists(const Puzzle& currentPuzzle,...

8

Your algorithm is plain $O(n)$. If you double the number of nodes, your runtime doubles. If you double the number of nodes at the current level, you also double the total number of nodes (or are you planning an unbalanced tree?). Your algorithm is OK, but there are some deviations from the classics... The use of a queue here is not quite right, or, ...

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

There are several places in this code where a loop is redundant(or at least can be simplified). For instance, this for loop: int index = 0; while ((index != oldList.size()) && (!oldList.get(index).equals(destination))) { index++; } can be substituted with a call to the contains method(the index of the element is not used, anyway. It just checks ...

8

I agree with Mathias Ettinger's use of sets and deques, with two changes: name the set seen instead of visited, because your algorithm adds to set before visiting. add the root to seen before entering while loop. Otherwise the root may be revisited (eg test case below where 1 points back to 0). import collections def bfs(graph, root): seen, queue = ...

8

I'll ignore the 'PluralSight' code. Note that you have implemented a breadth-first traversal. As far as I'm concerned, a spec which doesn't specify how the tree is traversed is insufficient, but you must document this behaviour (e.g. with inline documentation (///), or otherwise make a statement that the order is undefined (otherwise people will unwittingly ...

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'm a fan of developing to interfaces and language-provided immutability, so I've refactored your Node and Edge classes to that end: INode interface: public interface INode { string Name { get; } IEnumerable<IEdge> Edges { get; } void AddEdge(INode targetNode, double weight); } IEdge interface: public interface IEdge { INode ...

7

One way to simplify the problem is a shift of datastructure to hold your islands. By converting the grid to a set containing only the "land" parts, you can speed up the computation by entirely removing the check for "does it fit into the map". The idea here is to pick a land in your set — doing so you'll know that you have discovered a new island — and ...

7

Will be fixed soon Advice 1 In BFS, you don't really need colors. (See alternative implementation.) Advice 2 (Exposing internals) public: std::vector<Vertex> vertices; std::vector< std::list<int> > adjList; I suggest you put the two fields under private:. Advice 3 Since an undirected graph is a special case of a directed graph (...

7

PEP-0008: your method names should follow snake_case style, and there should be a space between arguments. So change your method singature to: def breadth_first_search(self, root): # remaining code You maintain a list called as visited, however the nodes added in it are ones which are yet to be visited. Call it to_visit instead. One should use the ...

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

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

Is this the correct method? No. You are trying to derive the level number from a flat list of nodes and some power of 2. This will only work with a complete balanced binary search tree, and you didn't mention such requirements to be present. To see a bad example, insert -4 to your existing sample. The resulting tree: 5 1 8 -...

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

Treatment of Keys You're doing a whole lot of extra work - both in terms of actual operations and code - the way you're treating keys. You're copying the entire maze everytime you get a key, and doing a whole separate search. That is unnecessary effort. Consider the canonical breadth-first-search double loop: while Q is not empty: u = Q.dequeue() ...

6

First, Queue is an unnecessary abstraction. JS arrays already provide methods to make it act like a queue. Use them directly instead. Next is that your logic is peppered with console.log calls, especially the visually annoying ######### lines. I suggest you make a helper function that accepts a message. That helper message can then do the formatting, saving ...

6

Pointer to vector? You have two members: a pointer to a vector (which you new, but never delete, which leads to several other problems) and its size. But you're already using a vector, so just do it twice: std::vector<std::vector<int>> adjacency_vector; Graph(int num_vertices) : adjacency_vector(num_vertices) { } Pointer to pair? Similarly, ...

6

I'd say that this code has the right amount of verbosity - not too terse, not too wordy. It's very readable, with one exception I'll mention below. In order to assess the performance, I'd probably need to implement it myself a couple different ways. I don't doubt it could be better, but don't have any great suggestions there. (Although, a depth-first search ...

6

It seems that someone has copied @MathiasEttinger's answer claiming it as their own and posted another question on CR asking for feedback on "their" solution. So here are my improvements to @MathiasEttinger's solution (originally posted here): Overall this code is pretty good. Well organized, sufficient commenting, good spacing, good use of pythonic ...

6

I think you can potentially remove the impact of the network altogether by using offline Wikipedia dumps. Wikipedia itself asks to not crawl them: Suppose you are building a piece of software that at certain points displays information that came from Wikipedia. If you want your program to display the information in a different way than can be seen ...

5

I managed to greatly increase performance by avoiding array resizing and memory reallocation. By allocating all array space I need by start and reusing those arrays instead of recreating and resizing them, the performance of the code has dramatically changed from one search every couple seconds to almost a hundred searches per second. <?php /* ...

5

I think BFS is your algorithm, but I do have some cleanups for you. The reason A* won't work is because your estimation of how much farther you have to go (you could do a simple grid distance from where you are to the end point, also considering the jump value where you are sitting) could be wrong based on future jumps, and in your case, estimations are not ...

5

Even though this is a brute-force enumeration algorithm, we can still make a few optimizations. Termination You check whether each puzzle is solved when you remove it from the queue. It would be more efficient to check when enqueuing it. The difference is that you won't realize that you've already solved the puzzle until after trying all of the other ...

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