This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Graph traversal" – news ·newspapers ·books ·scholar ·JSTOR(October 2014) (Learn how and when to remove this message)

Incomputer science,graph traversal (also known asgraph search) refers to the process of visiting (checking and/or updating) each vertex in agraph. Such traversals are classified by the order in which the vertices are visited.Tree traversal is a special case of graph traversal.

Unlike tree traversal, graph traversal may require that some vertices be visited more than once, since it is not necessarily known before transitioning to a vertex that it has already been explored. As graphs become moredense, this redundancy becomes more prevalent, causing computation time to increase; as graphs become more sparse, the opposite holds true.

Thus, it is usually necessary to remember which vertices have already been explored by the algorithm, so that vertices are revisited as infrequently as possible (or in the worst case, to prevent the traversal from continuing indefinitely). This may be accomplished by associating each vertex of the graph with a "color" or "visitation" state during the traversal, which is then checked and updated as the algorithm visits each vertex. If the vertex has already been visited, it is ignored and the path is pursued no further; otherwise, the algorithm checks/updates the vertex and continues down its current path.

Several special cases of graphs imply the visitation of other vertices in their structure, and thus do not require that visitation be explicitly recorded during the traversal. An important example of this is a tree: during a traversal it may be assumed that all "ancestor" vertices of the current vertex (and others depending on the algorithm) have already been visited. Both thedepth-first andbreadth-first graph searches are adaptations of tree-based algorithms, distinguished primarily by the lack of a structurally determined "root" vertex and the addition of a data structure to record the traversal's visitation state.

Note. — If each vertex in a graph is to be traversed by a tree-based algorithm (such as DFS or BFS), then the algorithm must be called at least once for eachconnected component of the graph. This is easily accomplished by iterating through all the vertices of the graph, performing the algorithm on each vertex that is still unvisited when examined.

A depth-first search (DFS) is an algorithm for traversing a finite graph. DFS visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth. A stack (often the program'scall stack viarecursion) is generally used when implementing the algorithm.

The algorithm begins with a chosen "root" vertex; it then iteratively transitions from the current vertex to an adjacent, unvisited vertex, until it can no longer find an unexplored vertex to transition to from its current location. The algorithm thenbacktracks along previously visited vertices, until it finds a vertex connected to yet more uncharted territory. It will then proceed down the new path as it had before, backtracking as it encounters dead-ends, and ending only when the algorithm has backtracked past the original "root" vertex from the very first step.

DFS is the basis for many graph-related algorithms, includingtopological sorts andplanarity testing.

• Input: A graphG and a vertexv ofG.
• Output: A labeling of the edges in the connected component ofv as discovery edges and back edges.

procedure DFS(G,v)is    labelv as exploredfor all edgese inG.incidentEdges(v)doif edgee is unexploredthenw ←G.adjacentVertex(v,e)if vertexw is unexploredthen                labele as a discovered edge                recursively call DFS(G,w)else               labele as a back edge

This sectionneeds expansion. You can help byadding to it.(October 2012)

A breadth-first search (BFS) is another technique for traversing a finite graph. BFS visits the sibling vertices before visiting the child vertices, and aqueue is used in the search process. This algorithm is often used to find the shortest path from one vertex to another.

• Input: A graphG and a vertexv ofG.
• Output: The closest vertex tov satisfying some conditions, or null if no such vertex exists.

procedure BFS(G,v)is    create a queueQ    enqueuev ontoQ    markvwhileQ is not emptydow ←Q.dequeue()ifw is what we are looking forthen            returnwfor all edgese inG.adjacentEdges(w)dox ←G.adjacentVertex(w,e)ifx is not markedthen                markx                enqueuex ontoQreturn null

Breadth-first search can be used to solve many problems in graph theory, for example:

• finding all vertices within oneconnected component;
• Cheney's algorithm;
• finding theshortest path between two vertices;
• testing a graph forbipartiteness;
• Cuthill–McKee algorithm mesh numbering;
• Ford–Fulkerson algorithm for computing themaximum flow in aflow network;
• serialization/deserialization of a binary tree vs serialization in sorted order (allows the tree to be re-constructed in an efficient manner);
• maze generation algorithms;
• flood fill algorithm for marking contiguous regions of a two dimensional image or n-dimensional array;
• analysis of networks and relationships.

The problem of graph exploration can be seen as a variant of graph traversal. It is anonline 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 graphG = (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 are known. The goal is to visit alln 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 thetravelling 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 simplegreedy algorithm:

• In the undirected case, the greedy tour is at mostO(lnn)-times longer than an optimal tour.^[1] The best lower bound known for any deterministic online algorithm is 10/3.^[2]
  • Unit weight undirected graphs can be explored with a competitive ration of2 −ε,^[3] which is already a tight bound onTadpole graphs.^[4]
• In the directed case, the greedy tour is at most (n − 1)-times longer than an optimal tour. This matches the lower bound ofn − 1.^[5] An analogous competitive lower bound ofΩ(n) also holds for randomized algorithms that know the coordinates of each node in a geometric embedding. If instead of visiting all nodes just a single "treasure" node has to be found, the competitive bounds areΘ(n²) on unit weight directed graphs, for both deterministic and randomized algorithms.

This sectionneeds expansion. You can help byadding to it.(December 2016)

Auniversal traversal sequence is a sequence of instructions comprising a graph traversal for anyregular graph with a set number of vertices and for any starting vertex. A probabilistic proof was used by Aleliunas et al. to show that there exists a universal traversal sequence with number of instructions proportional toO(n⁵) for any regular graph withn vertices.^[6] The steps specified in the sequence are relative to the current node, not absolute. For example, if the current node isv_j, andv_j hasd neighbors, then the traversal sequence will specify the next node to visit,v_j+1, as thei^th neighbor ofv_j, where 1 ≤i ≤d.

• External memory graph traversal

• Graph algorithms

• CS1: long volume value
• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from October 2014
• All articles needing additional references
• Articles to be expanded from October 2012
• All articles to be expanded
• Articles to be expanded from December 2016
• Articles with example pseudocode