Graph traversal: Difference between revisions

Revision as of 20:17, 11 July 2017

Latest revision as of 19:01, 4 June 2025

(49 intermediate revisions by 37 users not shown)

Line 1:

{{redirect-distinguish|Graph search|Facebook Graph Search}}

{{Short description|Computer science algorithm}}

{{refimprove|date=October 2014}}

{{Graph search algorithm}}

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 ljuualtoto 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.

Line 13:

==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 entirely[[connected distinctcomponent subgraph(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===

Line 27:

* ''Output'': A labeling of the edges in the connected component of ''v'' as discovery edges and back edges.

1 '''procedure''' DFS(''G'', ''v''): '''is'''

2 label ''v'' as explored

3 '''for all''' edges ''e'' in ''G''.incidentEdges(''v'') '''do'''

4 '''if''' edge ''e'' is unexplored '''then'''

5 ''w'' ← ''G''.adjacentVertex(''v'', ''e'')

6 '''if''' vertex ''w'' is unexplored '''then'''

7 label ''e'' as a discovered edge

8 recursively call DFS(''G'', ''w'')

9 '''else'''

10 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 neighborsibling 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 a vertex exists.

1 '''procedure''' BFS(''G'', ''v''): '''is'''

2 create a queue ''Q''

3 enqueue ''v'' onto ''Q''

4 mark ''v''

5 '''while''' ''Q'' is not empty: '''do'''

6 ''tw'' ← ''Q''.dequeue()

7 '''if''' ''tw'' is what we are looking for: '''then'''

8 return ''tw''

9 '''for all''' edges ''e'' in ''G''.adjacentEdges(''tw'') '''do'''

12 ''ox'' ← ''G''.adjacentVertex(''tw'', ''e'')

13 '''if''' ''ox'' is not marked: '''then'''

14 mark ''ox''

15 enqueue ''ox'' onto ''Q''

16 '''return''' null

==Applications==

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 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 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]]:

* 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 {{nowrap|210/3.5 − ''ε''}};<ref>{{cite journal |last1=DobrevBirx |first1=StefanAlexander |last2=KrálovicDisser |first2=RastislavYann |last3=MarkouHopp |first3=EuripidesAlexander V. |titlelast4=OnlineKarousatou Graph Exploration|first4=Christina with Advice|journaltitle=Proc.An ofimproved thelower 19thbound Internationalfor Colloquiumcompetitive ongraph Structuralexploration Information|journal=Theoretical andComputer CommunicationScience Complexity (SIROCCO)|date=2012May 2021 |volume=868 |pages=65–86 |doi=10.10071016/978-3-642-31104-8_23j.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²''²) on unit weight directed graphs, for both deterministic and randomized algorithms.

==Universal Traversaltraversal Sequencessequences==

{{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 <math display="inline">{{nowrap|''O\left''(''n^''<sup>5\right)</mathsup>)}} for any regular graph with ''n'' vertices.<ref>{{cite journalbook|last1=Aleliunas|first1=R.|last2=Karp|first2=R.|last3=Lipton|first3=R.|last4=Lovász|first4=L.|last5=Rackoff|first5=C. |title=20th Annual Symposium on Foundations of Computer Science (SFCS 1979) |chapter=Random walks, universal traversal sequences, and the complexity of maze problems |journalpages=20th Annual Symposium on Foundations of Computer Science (sfcs 1979)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''_''j'', and ''v''_''j'' has ''d'' neighbors, then the traversal sequence will specify the next node to visit, ''v''_''j''+1, as the ''i''^th neighbor of ''v''_''j'', where 1 ≤ ''i'' ≤ ''d''.

relative to the current node, not absolute. For example, if the current node is v_j, and v_j has ''d'' neighbors, then the traversal sequence will specify the next node to visit, v_j+1, as the ''i''^th neighbor of v_j, 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]]