Depth-first search (original) (raw)

About DBpedia

بحث تعمقي الأولوية / عامودي الأولوية أو البحث المتعمق (DFS) هو خوارزمية للعبور أو البحث داخل شجرة أو هياكل البيانات كالرسمة البيانية (graph). يبدأ المرء في الجذر (اختيار نقطة من الشجرة لتكون جذر وهي النقطة نفسها التي بدأ منها البحث) ويستكشف قدر الإمكان على طول كل فرع قبل التراجع. تحققت النسخة الأولى من البحث المتعمق الأول في القرن ال19 من قبل عالم الرياضيات الفرنسي بيير تشارلز تريماو كإستراتيجية لحل المتاهات.

thumbnail

Property Value
dbo:abstract بحث تعمقي الأولوية / عامودي الأولوية أو البحث المتعمق (DFS) هو خوارزمية للعبور أو البحث داخل شجرة أو هياكل البيانات كالرسمة البيانية (graph). يبدأ المرء في الجذر (اختيار نقطة من الشجرة لتكون جذر وهي النقطة نفسها التي بدأ منها البحث) ويستكشف قدر الإمكان على طول كل فرع قبل التراجع. تحققت النسخة الأولى من البحث المتعمق الأول في القرن ال19 من قبل عالم الرياضيات الفرنسي بيير تشارلز تريماو كإستراتيجية لحل المتاهات. (ar) Prohledávání do hloubky (v angličtině označované jako depth-first search nebo zkratkou DFS) je grafový algoritmus pro procházení grafů metodou backtrackingu. Pracuje tak, že vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil. Pokud narazí na vrchol, z nějž už nelze dále pokračovat (nemá žádné následníky nebo byli všichni navštíveni), vrací se zpět backtrackingem. (cs) Una cerca en profunditat (en anglès Depth First Search, DFS) és un algorisme que permet recórrer tots els nodes d'un arbre o graf de manera ordenada, però no uniforme. El seu funcionament es basa a anar expandint cada que troba, de manera recursiva, recorrent tots els nodes d'un camí concret. Quan ja no queden més nodes per visitar d'aquest camí, es realitza un pas enrere (Backtracking), que permet que pugui tornar a començar el mateix procés amb cadascun dels germans d'un node ja processat. De la mateixa manera, existeix l'algorisme de cerca en amplada (BFS - breadth first search). El segle xix, el matemàtic francès investigà una versió de l'algorisme de cerca en profunditat com a estratègia per a la . (ca) Ο αλγόριθμος Αναζήτησης Κατά Βάθος (DFS - Depth-first search) επιτυγχάνει διάσχιση ή αναζήτηση σε δέντρο ή γράφημα. Η διάσχιση ξεκινά από τη ρίζα και εξερευνά όσο το δυνατόν περισσότερο κατά μήκος κάθε κλαδί του δέντρου μέχρι να φτάσει σε αδιέξοδο. Μια έκδοση της αναζήτησης κατά βάθος ερευνήθηκε κατά τον 19ο αιώνα από τον Γάλλο μαθηματικό ως μια στρατηγική για την επίλυση λαβυρίνθων. Ένας λαβύρινθος μπορεί να αναπαρασταθεί ως γράφος θεωρώντας κάθε διασταύρωση του λαβύρινθου ως κόμβος και κάθε εσωτερική διαδρομή ως ακμή . (el) Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. 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. (en) Tiefensuche (englisch depth-first search, DFS) ist in der Informatik ein Verfahren zum Suchen von Knoten in einem Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Im Gegensatz zur Breitensuche wird bei der Tiefensuche zunächst ein Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden. Dabei sollen alle erreichbaren Knoten des Graphen besucht werden. Für Graphen mit potenziell wenigen, langen Pfaden bietet sich die beschränkte Tiefensuche an, bei der jeder Pfad nur bis zu einer bestimmten Tiefe beschritten wird. Eine Verbesserung der Tiefensuche ist die iterative Tiefensuche. (de) Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo de búsqueda no informada utilizado para recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado. Análogamente existe el algoritmo de búsqueda en anchura (BFS o Breadth First Search). (es) Sakonera bilaketa (ingelesez: DFS edo Depth First Search) informazioa erabiltzen ez duen bilaketa algoritmo bat da, zuhaitz (grafo teoria) edo grafo bateko nodo guztiak aztertu ahal izateko era ordenatu baina ez uniforme batean. Algoritmo horrek aurkitzen dituen nodo guztiak hedatzen ditu, era errekurtsiboan, ibilbide zehatz bat jarraituz. Ibilbide horretatik arakatutako nodo gehiago ez direnean geratzen, atzera bueltatzen da, eta prozesu berdina errepikatzen du prozesatutako nodoaren anai guztiekin. (eu) L'algorithme de parcours en profondeur (ou parcours en profondeur, ou DFS, pour Depth-First Search) est un algorithme de parcours d'arbre, et plus généralement de parcours de graphe. Il se décrit naturellement de manière récursive. Son application la plus simple consiste à déterminer s'il existe un chemin d'un sommet à un autre. (fr) 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. (ko) 深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。 (ja) Nella teoria dei grafi, la ricerca in profondità (in inglese depth-first search, in acronimo DFS), è un algoritmo di ricerca su alberi e grafi. A differenza della ricerca in ampiezza, ha la caratteristica di essere intrinsecamente ricorsivo. (it) Depth-first search (DFS) is een zoekalgoritme voor het doorzoeken van een boomstructuur of een graaf. Het algoritme begint bij de wortel (of eender welke knoop bij een graaf) en kiest een tak en doorzoekt deze zo ver mogelijk, zonder terug te keren op vorige stappen. (nl) Przeszukiwanie w głąb (ang. Depth-first search, w skrócie DFS) – algorytm przeszukiwania grafu. Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi wychodzących z podanego wierzchołka. Po zbadaniu wszystkich krawędzi wychodzących z danego wierzchołka algorytm powraca do wierzchołka, z którego dany wierzchołek został odwiedzony. (pl) Djup-först-sökning (dfs) är en strategi för att traversera ett träd (en hierarkisk datastruktur där varje nod kan ha noll eller flera underordnade noder) där man följer varje gren i trädet till dess yttersta nod (dess löv) innan man backar upp i hierarkin och väljer nästa gren att undersöka. I vilken ordning grenarna i trädet genomsöks definieras av implementationen. I bilden till höger kommer man med djup-först sökning från roten (nod 8) att i tur och ordning undersöka noderna enligt någon av följande ordningar: * 8, 3, 1, 6, 4, 7, 10, 14, 13; * 8, 10, 14, 13, 3, 1, 6, 4, 7; * 8, 3, 6, 4, 7, 1, 10, 14, 13; * osv Strategin kan vara värdefull i många sammanhang och anledningen att välja den beror naturligtvis på vilken data som trädet organiserar. I till exempel ett beslutsträd (ett träd som spänner upp tänkbara konsekvenser av en serie beslut, t.ex. drag i ett schackparti eller en serie strategiska affärsbeslut) utforskar man med denna strategi den yttersta konsekvensen av en viss serie beslut innan man tittar på alternativa beslut. Med djup först sökning går det alltid att hitta ett per definition framgångsrikt resultat (till exempel vinst i ett schackparti) om ett sådant finns i trädet, men det finns ingen garanti för att hitta en optimal väg till detta resultat. (sv) Na teoria dos grafos, busca em profundidade (ou busca em profundidade-primeiro, também conhecido em inglês por Depth-First Search - DFS) é um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo. Intuitivamente, o algoritmo começa num nó raiz (selecionando algum nó como sendo o raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder(backtracking). Uma versão da busca em profundidade foi investigada no século XIX pelo matemático francês como estratégia para solucionar labirintos. (pt) Алгори́тм по́шуку в глибину́ (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графу. Робота алгоритму починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину. (uk) 深度优先搜索算法（英語：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。 深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如无权最长路径问题等等。 因发明“深度优先搜索算法”，約翰·霍普克洛夫特与罗伯特·塔扬在1986年共同获得计算机领域的最高奖：图灵奖。 (zh) Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин. (ru)
dbo:thumbnail wiki-commons:Special:FilePath/Depth-first-tree.svg?width=300
dbo:wikiPageExternalLink http://quickgraph.codeplex.com/Wiki/View.aspx%3Ftitle=Depth%20First%20Search%20Example http://www.algolist.net/Algorithms/Graph_algorithms/Undirected/Depth-first_search http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm http://opendatastructures.org/versions/edition-0.1e/ods-java/12_3_Graph_Traversal.html%23SECTION001532000000000000000 https://code.google.com/p/yagsbpl/ http://www.cs.duke.edu/csed/jawaa/DFSanim.html http://www.boost.org/libs/graph/doc/depth_first_search.html http://www-cs-faculty.stanford.edu/~knuth/taocp.html
dbo:wikiPageID 97034 (xsd:integer)
dbo:wikiPageLength 20535 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1123439738 (xsd:integer)
dbo:wikiPageWikiLink dbr:Pat_Morin dbr:Primogeniture dbr:Binary_trees dbr:Algorithm dbr:Bias dbr:Charles_Pierre_Trémaux dbr:Decision_problem dbr:Degree_(graph_theory) dbr:Introduction_to_Algorithms dbr:Limit_set dbr:Thomas_H._Cormen dbr:Search_game dbc:Articles_containing_video_clips dbc:Search_algorithms dbr:Commonwealth_realms dbr:Control-flow_graph dbr:Analysis_of_algorithms dbr:Maze_solving_algorithm dbr:Memory_management dbr:Clifford_Stein dbr:Graph_(data_structure) dbr:Branching_factor dbr:NC_(complexity) dbr:Tree_data_structure dbr:Stack_(abstract_data_type) dbr:Parallel_algorithm dbr:Polish_notation dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbr:Time_complexity dbr:Topological_sorting dbr:Tree_(data_structure) dbr:Tree_traversal dbr:P-complete dbr:Trémaux_tree dbr:Edge_(graph_theory) dbr:Breadth-first_search dbr:Bridge_(graph_theory) dbr:Graph_theory dbr:Iterator dbr:John_Reif dbr:File:MAZE_30x20_DFS.ogv dbr:Depth-limited_search dbr:Reverse_Polish_notation dbr:Group_(mathematics) dbr:Halting_problem dbr:Heuristics dbr:Iterative_deepening_depth-first_search dbr:Artificial_intelligence dbr:Charles_E._Leiserson dbr:Biconnected_graph dbr:Parse_tree dbr:Directed_acyclic_graph dbr:Connected_component_(graph_theory) dbr:Maze_generation dbr:Search_algorithm dbr:Maze dbr:Sample_(statistics) dbr:Vertex_(graph_theory) dbr:Planarity_testing dbr:Spanning_tree_(mathematics) dbr:Ronald_L._Rivest dbr:Strongly_connected_components dbr:File:Depth-First-Search.gif dbr:File:Depth-first-tree.svg dbr:File:Graph.traversal.example.svg dbr:File:If-then-else-control-flow-graph.svg dbr:File:Tree_edges.svg
dbp:bot InternetArchiveBot (en)
dbp:class dbr:Search_algorithm
dbp:complete yes (en)
dbp:data dbr:Graph_(data_structure)
dbp:date October 2022 (en)
dbp:fixAttempted yes (en)
dbp:optimal no (en)
dbp:space if entire graph is traversed without repetition, O = for implicit graphs without elimination of duplicate nodes (en)
dbp:time for explicit graphs traversed without repetition, for implicit graphs with branching factor b searched to depth d (en)
dbp:wikiPageUsesTemplate dbt:Graph_search_algorithm dbt:Citation dbt:Commons_category dbt:Dead_link dbt:ISBN dbt:Mvar dbt:Refbegin dbt:Refend dbt:Refimprove dbt:Reflist dbt:Rp dbt:Short_description dbt:Infobox_algorithm
dcterms:subject dbc:Articles_containing_video_clips dbc:Search_algorithms dbc:Articles_with_example_pseudocode dbc:Graph_algorithms
rdf:type yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:comment بحث تعمقي الأولوية / عامودي الأولوية أو البحث المتعمق (DFS) هو خوارزمية للعبور أو البحث داخل شجرة أو هياكل البيانات كالرسمة البيانية (graph). يبدأ المرء في الجذر (اختيار نقطة من الشجرة لتكون جذر وهي النقطة نفسها التي بدأ منها البحث) ويستكشف قدر الإمكان على طول كل فرع قبل التراجع. تحققت النسخة الأولى من البحث المتعمق الأول في القرن ال19 من قبل عالم الرياضيات الفرنسي بيير تشارلز تريماو كإستراتيجية لحل المتاهات. (ar) Prohledávání do hloubky (v angličtině označované jako depth-first search nebo zkratkou DFS) je grafový algoritmus pro procházení grafů metodou backtrackingu. Pracuje tak, že vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil. Pokud narazí na vrchol, z nějž už nelze dále pokračovat (nemá žádné následníky nebo byli všichni navštíveni), vrací se zpět backtrackingem. (cs) Ο αλγόριθμος Αναζήτησης Κατά Βάθος (DFS - Depth-first search) επιτυγχάνει διάσχιση ή αναζήτηση σε δέντρο ή γράφημα. Η διάσχιση ξεκινά από τη ρίζα και εξερευνά όσο το δυνατόν περισσότερο κατά μήκος κάθε κλαδί του δέντρου μέχρι να φτάσει σε αδιέξοδο. Μια έκδοση της αναζήτησης κατά βάθος ερευνήθηκε κατά τον 19ο αιώνα από τον Γάλλο μαθηματικό ως μια στρατηγική για την επίλυση λαβυρίνθων. Ένας λαβύρινθος μπορεί να αναπαρασταθεί ως γράφος θεωρώντας κάθε διασταύρωση του λαβύρινθου ως κόμβος και κάθε εσωτερική διαδρομή ως ακμή . (el) Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. 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. (en) Sakonera bilaketa (ingelesez: DFS edo Depth First Search) informazioa erabiltzen ez duen bilaketa algoritmo bat da, zuhaitz (grafo teoria) edo grafo bateko nodo guztiak aztertu ahal izateko era ordenatu baina ez uniforme batean. Algoritmo horrek aurkitzen dituen nodo guztiak hedatzen ditu, era errekurtsiboan, ibilbide zehatz bat jarraituz. Ibilbide horretatik arakatutako nodo gehiago ez direnean geratzen, atzera bueltatzen da, eta prozesu berdina errepikatzen du prozesatutako nodoaren anai guztiekin. (eu) L'algorithme de parcours en profondeur (ou parcours en profondeur, ou DFS, pour Depth-First Search) est un algorithme de parcours d'arbre, et plus généralement de parcours de graphe. Il se décrit naturellement de manière récursive. Son application la plus simple consiste à déterminer s'il existe un chemin d'un sommet à un autre. (fr) 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. (ko) 深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。 (ja) Nella teoria dei grafi, la ricerca in profondità (in inglese depth-first search, in acronimo DFS), è un algoritmo di ricerca su alberi e grafi. A differenza della ricerca in ampiezza, ha la caratteristica di essere intrinsecamente ricorsivo. (it) Depth-first search (DFS) is een zoekalgoritme voor het doorzoeken van een boomstructuur of een graaf. Het algoritme begint bij de wortel (of eender welke knoop bij een graaf) en kiest een tak en doorzoekt deze zo ver mogelijk, zonder terug te keren op vorige stappen. (nl) Przeszukiwanie w głąb (ang. Depth-first search, w skrócie DFS) – algorytm przeszukiwania grafu. Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi wychodzących z podanego wierzchołka. Po zbadaniu wszystkich krawędzi wychodzących z danego wierzchołka algorytm powraca do wierzchołka, z którego dany wierzchołek został odwiedzony. (pl) Na teoria dos grafos, busca em profundidade (ou busca em profundidade-primeiro, também conhecido em inglês por Depth-First Search - DFS) é um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo. Intuitivamente, o algoritmo começa num nó raiz (selecionando algum nó como sendo o raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder(backtracking). Uma versão da busca em profundidade foi investigada no século XIX pelo matemático francês como estratégia para solucionar labirintos. (pt) Алгори́тм по́шуку в глибину́ (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графу. Робота алгоритму починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину. (uk) 深度优先搜索算法（英語：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。 深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如无权最长路径问题等等。 因发明“深度优先搜索算法”，約翰·霍普克洛夫特与罗伯特·塔扬在1986年共同获得计算机领域的最高奖：图灵奖。 (zh) Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин. (ru) Una cerca en profunditat (en anglès Depth First Search, DFS) és un algorisme que permet recórrer tots els nodes d'un arbre o graf de manera ordenada, però no uniforme. El seu funcionament es basa a anar expandint cada que troba, de manera recursiva, recorrent tots els nodes d'un camí concret. Quan ja no queden més nodes per visitar d'aquest camí, es realitza un pas enrere (Backtracking), que permet que pugui tornar a començar el mateix procés amb cadascun dels germans d'un node ja processat. De la mateixa manera, existeix l'algorisme de cerca en amplada (BFS - breadth first search). (ca) Tiefensuche (englisch depth-first search, DFS) ist in der Informatik ein Verfahren zum Suchen von Knoten in einem Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Im Gegensatz zur Breitensuche wird bei der Tiefensuche zunächst ein Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden. Dabei sollen alle erreichbaren Knoten des Graphen besucht werden. Für Graphen mit potenziell wenigen, langen Pfaden bietet sich die beschränkte Tiefensuche an, bei der jeder Pfad nur bis zu einer bestimmten Tiefe beschritten wird. (de) Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo de búsqueda no informada utilizado para recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado. (es) Djup-först-sökning (dfs) är en strategi för att traversera ett träd (en hierarkisk datastruktur där varje nod kan ha noll eller flera underordnade noder) där man följer varje gren i trädet till dess yttersta nod (dess löv) innan man backar upp i hierarkin och väljer nästa gren att undersöka. I vilken ordning grenarna i trädet genomsöks definieras av implementationen. I bilden till höger kommer man med djup-först sökning från roten (nod 8) att i tur och ordning undersöka noderna enligt någon av följande ordningar: (sv)
rdfs:label البحث المتعمق الأول (ar) Cerca en profunditat (ca) Prohledávání do hloubky (cs) Tiefensuche (de) Αναζήτηση Κατά Βάθος (el) Búsqueda en profundidad (es) Sakonera bilaketa (eu) Depth-first search (en) Algorithme de parcours en profondeur (fr) Ricerca in profondità (it) 深さ優先探索 (ja) 깊이 우선 탐색 (ko) Depth-first search (nl) Przeszukiwanie w głąb (pl) Busca em profundidade (pt) Поиск в глубину (ru) Djup-först-sökning (sv) Пошук у глибину (uk) 深度优先搜索 (zh)
owl:sameAs freebase:Depth-first search yago-res:Depth-first search wikidata:Depth-first search dbpedia-ar:Depth-first search dbpedia-bar:Depth-first search dbpedia-bg:Depth-first search dbpedia-ca:Depth-first search dbpedia-cs:Depth-first search dbpedia-de:Depth-first search dbpedia-el:Depth-first search dbpedia-es:Depth-first search dbpedia-et:Depth-first search dbpedia-eu:Depth-first search dbpedia-fa:Depth-first search dbpedia-fi:Depth-first search dbpedia-fr:Depth-first search dbpedia-he:Depth-first search http://hi.dbpedia.org/resource/गहराई_पहले_सर्च dbpedia-hu:Depth-first search http://hy.dbpedia.org/resource/Փնտրում_դեպի_խորություն dbpedia-it:Depth-first search dbpedia-ja:Depth-first search dbpedia-ka:Depth-first search dbpedia-ko:Depth-first search http://lt.dbpedia.org/resource/Paieška_į_gylį http://lv.dbpedia.org/resource/Meklēšana_dziļumā dbpedia-nl:Depth-first search dbpedia-no:Depth-first search dbpedia-pl:Depth-first search dbpedia-pt:Depth-first search dbpedia-ro:Depth-first search dbpedia-ru:Depth-first search dbpedia-simple:Depth-first search dbpedia-sr:Depth-first search dbpedia-sv:Depth-first search http://tl.dbpedia.org/resource/Paghahanap_na_lalim-muna dbpedia-tr:Depth-first search dbpedia-uk:Depth-first search dbpedia-vi:Depth-first search dbpedia-zh:Depth-first search https://global.dbpedia.org/id/4ySKj
prov:wasDerivedFrom wikipedia-en:Depth-first_search?oldid=1123439738&ns=0
foaf:depiction wiki-commons:Special:FilePath/Depth-First-Search.gif wiki-commons:Special:FilePath/Depth-first-tree.svg wiki-commons:Special:FilePath/Graph.traversal.example.svg wiki-commons:Special:FilePath/If-then-else-control-flow-graph.svg wiki-commons:Special:FilePath/Tree_edges.svg
foaf:isPrimaryTopicOf wikipedia-en:Depth-first_search
is dbo:wikiPageDisambiguates of dbr:DFS
is dbo:wikiPageRedirects of dbr:Applications_of_depth-first_search dbr:Depth-First_Search dbr:Depth-first_traversal dbr:DFS_algorithm dbr:Back_edge dbr:Forward_edge dbr:Depth-first dbr:Depth_First_Search dbr:Depth_first_search
is dbo:wikiPageWikiLink of dbr:Beam_search dbr:Beam_stack_search dbr:Prolog dbr:Envy-graph_procedure dbr:List_of_algorithms dbr:List_of_computing_and_IT_abbreviations dbr:Primogeniture dbr:Biconnected_component dbr:Binary_tree dbr:Bowtie_(sequence_analysis) dbr:Branch_and_bound dbr:Algebraic_Logic_Functional_programming_language dbr:Algorithmic_technique dbr:Aperiodic_graph dbr:List_of_graph_theory_topics dbr:Pathfinding dbr:Cycle_(graph_theory) dbr:Dominance_drawing dbr:Dovetailing_(computer_science) dbr:Dynamic_connectivity dbr:Indra's_Pearls_(book) dbr:Intersection_non-emptiness_problem dbr:LASCNN_algorithm dbr:Lexicographic_breadth-first_search dbr:Space_hierarchy_theorem dbr:Weak_component dbr:Control-flow_graph dbr:Md5deep dbr:SL_(complexity) dbr:Chemical_database dbr:Gas_networks_simulation dbr:Generalized_geography dbr:Strahler_number dbr:Fringe_search dbr:Graph_coloring dbr:Concolic_testing dbr:Connected-component_labeling dbr:Cooley–Tukey_FFT_algorithm dbr:Applications_of_depth-first_search dbr:Ariadne's_thread_(logic) dbr:Stack_(abstract_data_type) dbr:Claw-free_graph dbr:Complement_graph dbr:Component_(graph_theory) dbr:Depth-First_Search dbr:Depth-first_traversal dbr:Hopcroft–Karp_algorithm dbr:Partition_problem dbr:Spanning_tree dbr:Tamari_lattice dbr:Maze-solving_algorithm dbr:Maze_generation_algorithm dbr:State_space_search dbr:Büchi_automaton dbr:Topological_sorting dbr:Transitive_closure dbr:Transpose_graph dbr:Tree_(graph_theory) dbr:Tree_traversal dbr:Trie dbr:Data-flow_analysis dbr:Widest_path_problem dbr:Game_complexity dbr:DFS dbr:Linear_arboricity dbr:Linear_time_property dbr:Link_analysis dbr:Trémaux_tree dbr:Transitive_reduction dbr:A*_search_algorithm dbr:Curry_(programming_language) dbr:Alpha–beta_pruning dbr:Breadth-first_search dbr:Bridge_(graph_theory) dbr:Digital_topology dbr:Dinic's_algorithm dbr:Flood_fill dbr:Fluid_Concepts_and_Creative_Analogies dbr:Ford–Fulkerson_algorithm dbr:Graph_canonization dbr:Graph_theory dbr:Graph_traversal dbr:Left-right_planarity_test dbr:Strongly_connected_component dbr:Preorder_(disambiguation) dbr:2-satisfiability dbr:Iterative_deepening_depth-first_search dbr:Backtracking dbr:Backward_chaining dbr:Stable_roommates_problem dbr:Bipartite_graph dbr:Bipolar_orientation dbr:Bitstate_hashing dbr:Blossom_tree_(graph_theory) dbr:Sweble dbr:Symbolic_artificial_intelligence dbr:Eight_queens_puzzle dbr:Transposition_table dbr:Dijkstra's_algorithm dbr:Directed_acyclic_graph dbr:Association_rule_learning dbr:Boolean_satisfiability_algorithm_heuristics dbr:St-connectivity dbr:Citation_graph dbr:Greedy_number_partitioning dbr:Ultimate_tic-tac-toe dbr:DFS_algorithm dbr:IEEE_1394 dbr:In-place_algorithm dbr:Kosaraju's_algorithm dbr:Network_science dbr:Recursion_(computer_science) dbr:Search_algorithm dbr:Longest_path_problem dbr:Mastermind_(board_game) dbr:Multiple_inheritance dbr:SLD_resolution dbr:SPQR_tree dbr:Static_timing_analysis dbr:Subset_sum_problem dbr:Simplified_molecular-input_line-entry_system dbr:Strong_orientation dbr:Z-order_curve dbr:Euler_tour_technique dbr:External_memory_graph_traversal dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Path-based_strong_component_algorithm dbr:Octree dbr:The_Art_of_Computer_Programming dbr:Planarity_testing dbr:Planted_motif_search dbr:Sudoku_solving_algorithms dbr:Rocha–Thatte_cycle_detection_algorithm dbr:Multiway_number_partitioning dbr:Robbins'_theorem dbr:Reverse-search_algorithm dbr:Outline_of_artificial_intelligence dbr:Space_complexity dbr:Tree-walking_automaton dbr:Search_tree dbr:Back_edge dbr:String-searching_algorithm dbr:Strong_connectivity_augmentation dbr:Forward_edge dbr:Depth-first dbr:Depth_First_Search dbr:Depth_first_search
is foaf:primaryTopic of wikipedia-en:Depth-first_search