{"id":490,"date":"2007-08-13T22:05:51","date_gmt":"2007-08-13T22:05:51","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/08\/13\/traversing-graphs\/"},"modified":"2007-08-13T22:05:51","modified_gmt":"2007-08-13T22:05:51","slug":"traversing-graphs","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/08\/13\/traversing-graphs\/","title":{"rendered":"Traversing Graphs"},"content":{"rendered":"

One amusing thing in graph theory is graph traversal. Many of the interesting algorithms on graph
\nare ultimately based on the idea of iterating through the nodes of the graph in some order that is
\nrelated to the structure of the graph.<\/p>\n

There are two fundamental orders of graph traversal, known as breadth-first<\/em> and depth-first<\/em>.<\/p>\n

<\/p>\n

They’re actually hard to explain in a comprehensible way – but they’re pretty easy to understand by
\nexample. So let’s look at a graph, and do its depth-first and breadth-first traversals; then we’ll look at
\nsome pseudo-code to explain the details.<\/p>\n

\"traversal-graph.png\"<\/p>\n

We’ll start with a depth-first traversal from A. What we’ll do is visit A, and then go to one of its children, doing a p depth first traversal of as much of the graph as we can from that child of A. So suppose we go to D first. Then
\nwe’ll start doing a depth-first traversal from D – so we go to M. From M we go to H. From H to N. From N we can’t go anywhere else – so we go back to H, and go to its next child, which is L. L to Q; Q to J; J to P; P to O. Then we’re at a dead end again. So we go back to P. Since O is already visited, P is a dead end. So we go back to J. From J, we can to go E. From E to F; F to C, C to B, B to I, I to K, and K to G. Then everything has been visited, and we’re done. So the full depth-first traversal that we just did was A,D,M,H,N,L,Q,J,P,O,E,F,C,B,I,K,G. The depth-first does pretty much exactly what the name sounds like: it pushes deep into the graph as quickly as possible.<\/p>\n

The breadth-first traversal is quite different. It first visits everything 1 step from its start; then 2 steps from its start; then 3; and it preserves path ordering it each level. What I mean by that will become clear from the example.<\/p>\n

We start again with A. Then we visit each node adjacent to A: A, F, D. Then we visit each node adjacent to F: C, B, E.
\nThen we visit each node adjacent to D: M. Then each node adjacent to C; nothing unvisited yet. Then adjacent to B: I is unvisited. Then E: J. Then M: H, Q. Then I: K, G. Then J: P. Then H: N, L. Then we go through a bunch where there’s nothing unvisited, until we get to P, which gives us O. So the full ordering is: A, F, D, C, B, E, M, I, J, H, Q, K, G, P, N, L, O. <\/p>\n

To see what I mean about path ordering, let’s look at the paths to some of the vertices in the breadth-first traversal: A, AF, AD, AFC, AFB, AFE, ADM, AFBI, AFEJ, ADMH, ADMQ, … Since we visited F before we visited D, we’ll always visit things on paths through F before we visit things on paths of the same length through D. <\/p>\n

Another way of thinking about the traversals is as a way of generating a spanning tree for the graph. Here’s a depth-first spanning tree for our example graph. As you can see, the depth first approach
\ngenerates a very long, very narrow tree with a small number of branches. That’s what you’ll generally see in a depth first traversal.<\/p>\n

\"depth-first-tree.png\"<\/p>\n

And here’s a breadth-first spanning tree. The breadth first approach produces a much shallower,
\nbushier tree.<\/p>\n

\"breadth-first-tree.png\"<\/p>\n

Finally, a bit of pseudocode, to give you the details:<\/p>\n

\nDepth-First-Search<\/b>(Graph, Vertex, Visited):\nvisit(Vertex)\nadd Vertex to Visited\nfor each vertex vert<\/em> adjacent to Vertex in G:\nif vert<\/em> is not in Visited:\nDepth-First-Search<\/b>(Graph, vert<\/em>, Visited)\nend if\nend for\nend\n<\/pre>\n
\nBreadth-First-Search<\/b>(Graph, Vertex, Visited)\nlet queue<\/em> = new Queue\nadd Vertex to end of queue<\/em>\nwhile queue<\/em> is not empty:\nlet v<\/em> = remove-first(queue<\/em>)\nif v<\/em> is not in Visited:\nvisit(v<\/em>)\nadd v<\/em> to Visited\nfor each vertex w<\/em> adjacent to v<\/em> in G:\nadd w<\/em> to end of queue<\/em>\nend for\nend if\nend while\nend\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
One amusing thing in graph theory is graph traversal. Many of the interesting algorithms on graph are ultimately based on the idea of iterating through the nodes of the graph in some order that is related to the structure of the graph. There are two fundamental orders of graph traversal, known as breadth-first and depth-first.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-490","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7U","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/490","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=490"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/490\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=490"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=490"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=490"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}