Tagged: graphs

Trees and continuation passing style

For no reason in particular I decided to revisit tree traversal as a kind of programming kata. There are two main kinds of tree traversal:

  • Depth first – This is where you go all the way down a tree’s branches first before bubbling up to do work. With a tree like below, you’d hit c before doing any work since it’s the deepest part of the tree (assuming you iterated left first then right)
         a
        / \
       b   e
     /  \
    c    d
    
  • Breadth first – This is where you hit all the nodes at the level you’re on before going further. So with the same tree, you’d hit a, then b, then e, then c and d.

Being as I actually hate tree traversal, and having to think about it, I decided that whatever I write better be extensible and clean.

Depth first

Here is a simple DFS … Read more

Tech Talk: Path finding algorithms

Today’s tech talk was about path finding algorithms. The topic was picked because of a recent linked shared to reddit that visualized different algorithms. The neat thing about the link is that you can really see how different algorithms and heuristics modify the route.

In general, path finding algorithms are based off a breadth first search. At each iteration while walking through the graph you check the nearest neighbors you update what was the calculated weight of the path to get to that neighbor. If it was cheaper to get to the neighbor via your own node (than whoever visited it previously) you update the neighbors weight to reflect that. This is pretty much dijsktras algorithm. Disjkstra gives you the shortest path cost, but not necessarily the shortest path. To find the shortest path you mark each node with who its cheapest parent is (i.e. the node you need to … Read more