One possibility is to compute the lexicographically least topological order. The algorithm is to maintain a priority queue containing the nodes whose effective in-degree (over nodes not yet processed) is zero. Repeatedly dequeue the node with the least label, append it to the order, decrement the effective in-degrees of its successors, enqueue the ones that … Read more
Kruskal is O(E log E); your derivation is right. You could also say O(E log V) because E <= V * V, so log(E) <= 2 log(V) (I don’t know why I remember that, other than that I think a prof put that on an exam at one point…)
There were algorithms called A1 and A2. Later, it was proved that A2 was optimal and in fact also the best algorithm possible, so he gave it the name A* which symbolically includes all possible version numbers. Source: In 1964 Nils Nilsson invented a heuristic based approach to increase the speed of Dijkstra’s algorithm. This … Read more
Now there is a library: graphlib Graphlib is a JavaScript library that provides data structures for undirected and directed multi-graphs along with algorithms that can be used with them. Implements: directed and undirected graphs (does A -> B imply B -> A) multigraphs (multiple distinct named edges from A -> B) compound graphs (nodes can … Read more
I’m the author of Grokking Algorithms. Sorry for this error—Dijkstra’s algorithm does work on graphs with cycles, as long as it is a positive weight cycle. I have updated the errata page to reflect this error. Dijkstra’s doesn’t work on negative weight cycles, and here’s an image that explains why:
One approach would be a perimeter walk. Given a starting point anywhere along the edge of the shape, remember that point. Start the bounding box as just that point. Walk the perimeter using a clockwise rule set – if the point used to get to the current point was above, then first look right, then … Read more
Consider solving your problem with a pair of simpler, more manageable algorithms: one algorithm that reliably creates simple, pre-solved boards and another that rearranges flows to make simple boards more complex. The first part, building a simple pre-solved board, is trivial (if you want it to be) if you’re using n flows on an nxn … Read more
Each of your three sequences can be understood as a clique in a multigraph. Within a clique, every vertex is connected to every other vertex. The following graph represents your sample case with the edges in each clique colored red, blue, and green, respectively. As you have already shown, we can classify pairs of vertices … Read more
This whole problem is known as “Common Subexpression Elimination” or CSE. It is a slightly smaller version of the problem called “Graph Reduction” faced by the implementer of compilers for functional programming languages. Googling “Common Subexpression elimination algorithm” gives lots of solutions, though none that I can see especially for the constraints given by matrix … Read more
Finding articulation vertices is an application of DFS. In a nutshell, Apply DFS on a graph. Get the DFS tree. A node which is visited earlier is a “parent” of those nodes which are reached by it and visited later. If any child of a node does not have a path to any of the … Read more