You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 34.205.0.0/16 has been blocked (disabled) by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 05:44, 30 September 2026.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪Jon Kolbert‬. The reason given is Open proxy/Webhost: See the help page if you are affected .
- Start of block: 05:38, 21 February 2024
- Expiry of block: 05:38, 21 February 2029
Your current IP address is 34.205.141.108. The blocked range is 34.205.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((redirect-distinguish|Graph search|Facebook Graph Search))
((Short description|Computer science algorithm))
((refimprove|date=October 2014))

In [[computer science]], '''graph traversal''' (also known as '''graph search''') refers to the process of visiting (checking and/or updating) each vertex in a [[Graph (discrete mathematics)|graph]]. Such traversals are classified by the order in which the vertices are visited. [[Tree traversal]] is a special case of graph traversal.

==Redundancy==
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 more [[dense graph|dense]], 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 the [[Depth-first search|depth-first]] and [[Breadth-first search|breadth-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.

==Graph traversal algorithms==
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 each [[connected component (graph theory)|connected 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.

===Depth-first search===
((main|Depth-first search))
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's [[call stack]] via [[recursion (computer science)|recursion]]) 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 then [[backtracking|backtracks]] 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, including [[topological sort]]s and [[planarity testing]].

====Pseudocode====
* ''Input'': A graph ''G'' and a vertex ''v'' of ''G''.
* ''Output'': A labeling of the edges in the connected component of ''v'' as discovery edges and back edges.

 '''procedure''' DFS(''G'', ''v'') '''is'''
     label ''v'' as explored
     '''for all''' edges ''e'' in ''G''.incidentEdges(''v'') '''do'''
         '''if''' edge ''e'' is unexplored '''then'''
             ''w'' ← ''G''.adjacentVertex(''v'', ''e'')
             '''if''' vertex ''w'' is unexplored '''then'''
                 label ''e'' as a discovered edge
                 recursively call DFS(''G'', ''w'')
             '''else'''
                label ''e'' as a back edge

===Breadth-first search===
((main|Breadth-first search))
((expand section|date=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 a [[Queue (abstract data type)|queue]] is used in the search process. This algorithm is often used to find the shortest path from one vertex to another.

====Pseudocode====
* ''Input'': A graph ''G'' and a vertex ''v'' of ''G''.
* ''Output'': The closest vertex to ''v'' satisfying some conditions, or null if no such vertex exists.

 '''procedure''' BFS(''G'', ''v'') '''is'''
     create a queue ''Q''
     enqueue ''v'' onto ''Q''
     mark ''v''
     '''while''' ''Q'' is not empty '''do'''
         ''w'' ← ''Q''.dequeue()
         '''if''' ''w'' is what we are looking for '''then'''
             return ''w''
         '''for all''' edges ''e'' in ''G''.adjacentEdges(''w'') '''do'''
             ''x'' ← ''G''.adjacentVertex(''w'', ''e'')
             '''if''' ''x'' is not marked '''then'''
                 mark ''x''
                 enqueue ''x'' onto ''Q''
     '''return''' null

==Applications==
Breadth-first search can be used to solve many problems in graph theory, for example:
* finding all vertices within one [[connected component (graph theory)|connected component]];
* [[Cheney's algorithm]];
* finding the [[shortest path]] between two vertices;
* testing a graph for [[Bipartite graph|bipartite]]ness;
* [[Cuthill–McKee algorithm]] mesh numbering;
* [[Ford–Fulkerson algorithm]] for computing the [[maximum flow problem|maximum flow]] in a [[flow 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 algorithm]]s;
* [[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 algorithm|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 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]]: 
* In the undirected case, the greedy tour is at most ((nowrap|''O''(ln ''n'')))-times longer than an optimal tour.<ref>((cite journal|last1=Rosenkrantz|first1=Daniel J.|last2=Stearns|first2=Richard E.|last3=Lewis, II|first3=Philip M.|title=An Analysis of Several Heuristics for the Traveling Salesman Problem|journal=SIAM Journal on Computing|volume=6|issue=3|pages=563–581|doi=10.1137/0206041|year=1977|s2cid=14764079 ))</ref> The best lower bound known for any deterministic online algorithm is 10/3.<ref>((cite journal |last1=Birx |first1=Alexander |last2=Disser |first2=Yann |last3=Hopp |first3=Alexander V. |last4=Karousatou |first4=Christina |title=An improved lower bound for competitive graph exploration |journal=Theoretical Computer Science |date=May 2021 |volume=868 |pages=65–86 |doi=10.1016/j.tcs.2021.04.003|arxiv=2002.10958 |s2cid=211296296 ))</ref>
** Unit weight undirected graphs can be explored with a competitive ration of ((nowrap|2 − ''ε'')),<ref>((cite journal |last1=Miyazaki |first1=Shuichi |last2=Morimoto |first2=Naoyuki |last3=Okabe |first3=Yasuo |title=The Online Graph Exploration Problem on Restricted Graphs |journal=IEICE Transactions on Information and Systems |date=2009 |volume=E92-D |issue=9 |pages=1620–1627 |doi=10.1587/transinf.E92.D.1620|bibcode=2009IEITI..92.1620M |hdl=2433/226939 |s2cid=8355092 |hdl-access=free ))</ref> which is already a tight bound on [[Tadpole graph|Tadpole graphs]].<ref>((cite journal |last1=Brandt |first1=Sebastian |last2=Foerster |first2=Klaus-Tycho |last3=Maurer |first3=Jonathan |last4=Wattenhofer |first4=Roger |title=Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs |journal=Theoretical Computer Science |date=November 2020 |volume=839 |pages=176–185 |doi=10.1016/j.tcs.2020.06.007|arxiv=1903.00581 |s2cid=67856035 ))</ref>
* In the directed case, the greedy tour is at most (((nowrap|''n'' − 1)))-times longer than an optimal tour. This matches the lower bound of ((nowrap|''n'' − 1)).<ref>((cite journal|last1=Foerster|first1=Klaus-Tycho|last2=Wattenhofer|first2=Roger|title=Lower and upper competitive bounds for online directed graph exploration|journal=Theoretical Computer Science|date=December 2016|volume=655|pages=15–29|doi=10.1016/j.tcs.2015.11.017|url=https://zenodo.org/record/895821|doi-access=free))</ref> 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''<sup>2</sup>) on unit weight directed graphs, for both deterministic and randomized algorithms.

==Universal traversal sequences==
((expand section|date=December 2016))
A ''universal traversal sequence'' is a sequence of instructions comprising a graph traversal for any [[regular 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 to ((nowrap|''O''(''n''<sup>5</sup>))) for any regular graph with ''n'' vertices.<ref>((cite journal|last1=Aleliunas|first1=R.|last2=Karp|first2=R.|last3=Lipton|first3=R.|last4=Lovász|first4=L.|last5=Rackoff|first5=C.|title=Random walks, universal traversal sequences, and the complexity of maze problems|journal=20th Annual Symposium on Foundations of Computer Science (SFCS 1979)|pages=218–223|date=1979|doi=10.1109/SFCS.1979.34|s2cid=18719861 ))</ref> The steps specified in the sequence are relative to the current node, not absolute. For example, if the current node is ''v''<sub>''j''</sub>, and ''v''<sub>''j''</sub> has ''d'' neighbors, then the traversal sequence will specify the next node to visit, ''v''<sub>''j''+1</sub>, as the ''i''<sup>th</sup> neighbor of ''v''<sub>''j''</sub>, where 1 ≤ ''i'' ≤ ''d''.

==See also==
* [[External memory graph traversal]]

==References==
((reflist))

((Graph traversal algorithms))
((Data structures and algorithms))

[[Category:Graph algorithms]]
[[Category:Articles with example pseudocode]]

[[de:Suchverfahren#Suche in Graphen]]
[[pl:Przeszukiwanie grafu]]

Pages transcluded onto the current version of this page (help):

Graph traversal (edit)
Template:Ambox (view source) (template editor protected)
Template:Cite journal (view source) (protected)
Template:Data structures and algorithms (edit)
Template:Expand section (view source) (template editor protected)
Template:Find sources mainspace (view source) (template editor protected)
Template:Graph traversal algorithms (edit)
Template:Hlist/styles.css (view source) (protected)
Template:Main (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:More citations needed (view source) (template editor protected)
Template:Navbox (view source) (template editor protected)
Template:Nowrap (view source) (protected)
Template:Pagetype (view source) (protected)
Template:Redirect-distinguish (view source) (extended confirmed protected)
Template:Refimprove (view source) (template editor protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SDcat (view source) (protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Module:Arguments (view source) (protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:Find sources (view source) (template editor protected)
Module:Find sources/config (view source) (template editor protected)
Module:Find sources/links (view source) (template editor protected)
Module:Find sources/templates/Find sources mainspace (view source) (template editor protected)
Module:Format link (view source) (template editor protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Labelled list hatnote (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Navbar (view source) (protected)
Module:Navbar/configuration (view source) (protected)
Module:Navbar/styles.css (view source) (protected)
Module:Navbox (view source) (template editor protected)
Module:Navbox/configuration (view source) (template editor protected)
Module:Navbox/styles.css (view source) (template editor protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:Redirect-distinguish (view source) (extended confirmed protected)
Module:SDcat (view source) (protected)
Module:String (view source) (protected)
Module:TableTools (view source) (protected)
Module:Unsubst (view source) (protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to Graph traversal.

Retrieved from "https://en.wikipedia.org/wiki/Graph_traversal"