Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes; the time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is used to traverse an entire graph, takes time O, linear in the size of the graph. In these applications it uses space O in the worst case to store the stack of vertices on the current search path as well as the set of already-visited vertices. Thus, in this setting, the time and space bounds are the same as for breadth-first search and the choice of which of these two algorithms to use depends less on their complexity and more on the different properties of the vertex orderings the two algorithms produce. For applications of DFS in relation to specific domains, such as searching for solutions in artificial intelligence or web-crawling, the graph to be traversed is either too large to visit in its entirety or infinite.

In such cases, search is only performed to a limited depth. When search is performed to a limited depth, the time is still linear in terms of the number of expanded vertices and edges but the space complexity of this variant of DFS is only proportional to the depth limit, as a result, is much smaller than the space needed for searching to the same depth using breadth-first search. For such applications, DFS lends itself much better to heuristic methods for choosing a likely-looking branch; when an appropriate depth limit is not known a priori, iterative deepening depth-first search applies DFS with a sequence of increasing limits. In the artificial intelligence mode of analysis, with a branching factor greater than one, iterative deepening increases the running time by only a constant factor over the case in which the correct depth limit is known due to the geometric growth of the number of nodes per level. DFS may be used to collect a sample of graph nodes. However, incomplete DFS to incomplete BFS, is biased towards nodes of high degree.

For the following graph: a depth-first search starting at A, assuming that the left edges in the shown graph are chosen before right edges, assuming the search remembers visited nodes and will not repeat them, will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a Trémaux tree, a structure with important applications in graph theory. Performing the same search without remembering visited nodes results in visiting nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G. Iterative deepening is one technique to avoid this infinite loop and would reach all nodes. A convenient description of a depth-first search of a graph is in terms of a spanning tree of the vertices reached during the search. Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, cross edges, which do neither.

Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected all of its edges are tree edges or back edges. An enumeration of the vertices of a graph is said to be a DFS ordering if it is the possible output of the application of DFS to this graph. Let G = be a graph with n vertices. For σ = be a list of distinct elements of V, for v ∈ V ∖, let ν σ be the greatest i such that v i is a neighbor of v, if such a i exists, be 0 otherwise. Let σ = be an enumeration of the vertices of V; the enumeration σ is said to be a DFS ordering if, for all 1 < i ≤ n, v

Schlesisches Tor is a Berlin U-Bahn station on the and lines. It is located in eastern Kreuzberg, near Oberbaumbrücke, in the Bohemian quarter known as SO36; the station is named after one of the former city gates of Berlin built in the early 18th century. The exceptionally richly designed station opened on 18 February 1902, on the first Berlin U-Bahn line erected by the Siemens & Halske company. On 11/12 March 1945, this station was directly hit, the track area was damaged. During the division of Berlin after 13 August 1961, the station was the eastern terminus of the U1, as the final station, Warschauer Straße, was in East Berlin; the link was reopened in 1995. An intermediate station at the Spree river, Stralauer Tor, had been destroyed in 1945 and never reopened. Schlesisches Tor was an atmospheric location in the 1966 espionage film The Quiller Memorandum starring George Segal and Alec Guinness

Heermann's gull is a gull resident in the United States and extreme southwestern British Columbia, nearly all nesting on Isla Rasa in the Gulf of California. They are found near shores or well out to sea rarely inland; the species is named after nineteenth-century explorer and naturalist. This species looks distinctly different from other gulls. Adults have a medium gray body, blackish-gray wings and tail with white edges, a red bill with a black tip; the head is white in breeding plumage. Immatures resemble non-breeding adults but are darker and browner, the bill is flesh-colored or pink till the second winter. A few birds, no more than 1 in 200, have white primary coverts, which form a showy spot on the upper wing; this gull is unlikely to be confused with other species as it is the only white-headed, gray-bodied gull found on the west coast of North America. Calls are described as deep and similar in pattern to other gulls but is noticeably different in quality. Of the current population of about 150,000 pairs, 90% nest on the island of Isla Rasa off Baja California in the Gulf of California, with smaller colonies as far north as California and as far south as Nayarit.

After breeding, birds disperse to central California, less north as far as British Columbia and south as far as Guatemala. Some birds exhibit strong site fidelity to their nonbreeding territories, including a one-legged gull who resided for 17 years at the Loch Lomond Marina in San Rafael, California; the only known active breeding colony of Heermann's gull in the continental United States is located in Seaside, when a small number of gulls were observed nesting on artificial fill islands on Roberts Lake as of 1999. After the islands eroded away by 2007, the colony continued to nest on nearby rooftops. In June 2018, one of the colony's main nesting sites, the Seaside McDonald's, was destroyed by a drunk driving accident. In April 2019, after obtaining a permit from the City of Seaside, the Monterey Audubon Society deployed a floating artificial nesting island in Roberts Lake in an effort to restore nesting territory to the colony. Heermann's Gull eats small fish, marine invertebrates, insects and carrion.

This species nests colonially like many gulls. The nests are at densities as high as 110 nests per 100 m2, it lays grayish buff, to buff with gray and brown markings. Heermann's gull sometimes steals prey from other seabirds brown pelicans, with which it associates. Isla Rasa was declared a sanctuary in 1964. Egg-collecting and disturbance during the breeding season are discouraged. With the breeding colony concentrated on one small island this species is vulnerable to a catastrophic weather event; the success of the colony in any one year is dependent on the availability of prey and this is related to the ocean temperature changes brought about by El Niño. These factors have caused the IUCN to rate this bird as "Near Threatened". Howell, Steve N. G.. A Guide to the Birds of Mexico and Northern Central America. Oxford University Press. ISBN 0-19-854012-4. Sibley, David Allen; the Sibley Guide to Birds. New York: Knopf. P. 227. ISBN 0-679-45122-6. Images and movies of the Heermann's gull at ARKive BirdLife species factsheet for Larus heermanni "Heermann's gull media".

Internet Bird Collection. Heermann's gull photo gallery at VIREO Audio recordings of Heermann's gull on Xeno-canto