Graph traversal: Difference between revisions

Revision as of 20:05, 8 September 2017

Revision as of 18:49, 9 October 2017

Line 72:

* serialization/deserialization of a binary tree vs serialization in sorted order (allows the tree to be re-constructed in an efficient manner);

* [[maze generation algorithm]]s;

* [[Flood fill|flood fill]] algorithm]] for marking contiguous regions of a two dimensional image or n-dimensional array;

* analysis of networks and relationships.

==Graph exploration==

The problem of graph exploration can be seen as a variant of graph traversal. It is an online problem, meaning that the information about the graph is only revealed during the runtime of the algorithm. A common model is as follows: given a connected graph {{nowrap|1=''G'' = (''V'', ''E'')}} with non-negative edge weights. The algorithm starts at some vertex, and knows all incident outgoing edges and the vertices at the end of these edges—but not more. When a new vertex is visited, then again all incident outgoing edges and the vertices at the end of the edges are known. The goal is to visit all ''n'' vertices and return to the starting vertex, but the sum of the weights of the tour should be as small as possible. The problem can also be understood as a specific version of the [[travelling salesman problem]], where the salesman has to discover the graph on the go.

For general graphs, the best known algorithms for both undirected and directed graphs is a simple greedy algorithm: