| dbo:abstract |
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. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal. (en) En théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d'un graphe de proche en proche à partir d'un sommet initial. Un cas particulier important est le parcours d'arbre. Le mot parcours est également utilisé dans un sens différent, comme synonyme de chemin (un parcours fermé étant un circuit). (fr) 그래프 트래버설(영어: Graph traversal)은 그래프의 모든 꼭짓점들을 방문하는 것과 관련한 문제와 그 방법을 말한다. 트리 순회는 그래프 순회의 특수한 경우이다. 트리 순회와 달리, 일반적인 그래프 순회에서는, 각 꼭짓점들을 한 번 이상 방문하는 경우도 있다. 다른 모든 꼭짓점들을 연결시켜주는 트리의 루트같은 꼭짓점이 존재하지 않을 수도 있다. (ko) У комп'ютерних науках, пошук по графу (або обхід графа) це процес проходження (перевірки або оновлення) кожної вершини графа. Такі алгоритми пошуку класифікують відповідно до порядку проходження вершин. Пошук по дереву є особливим випадком пошуку по графу. (uk) 图的遍历问题分为四类： * 遍历完所有的边而不能有重复，即所謂“欧拉路径问题”（又名一笔画问题）； * 遍历完所有的顶点而没有重复，即所谓“哈密頓路径问题”。 * 遍历完所有的边而可以有重复，即所谓“中国邮递员问题”； * 遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。 对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。 第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。 (zh) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Graph-scan.png?width=300 |
| dbo:wikiPageID |
6263731 (xsd:integer) |
| dbo:wikiPageInterLanguageLink |
dbpedia-de:Suchverfahren dbpedia-pl:Przeszukiwanie_grafu |
| dbo:wikiPageLength |
11587 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1103034087 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Queue_(abstract_data_type) dbr:Topological_sort dbr:Dense_graph dbr:Regular_graph dbr:Cuthill–McKee_algorithm dbr:Depth-first_search dbr:Maximum_flow_problem dbr:Cheney's_algorithm dbr:Online_algorithm dbr:Graph_(discrete_mathematics) dbr:Call_stack dbr:Shortest_path dbr:Computer_science dbr:Maze_generation_algorithm dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbr:Travelling_salesman_problem dbr:Tree_traversal dbr:Flow_network dbr:Breadth-first_search dbr:Flood_fill dbr:Ford–Fulkerson_algorithm dbr:Backtracking dbr:Bipartite_graph dbr:Connected_component_(graph_theory) dbr:Greedy_algorithm dbr:Recursion_(computer_science) dbr:External_memory_graph_traversal dbr:Planarity_testing dbr:Tadpole_graph dbr:File:Graph-scan.png |
| dbp:wikiPageUsesTemplate |
dbt:Graph_search_algorithm dbt:Expand_section dbt:Main dbt:Redirect-distinguish dbt:Refimprove dbt:Reflist dbt:Short_description |
| dct:subject |
dbc:Articles_with_example_pseudocode dbc:Graph_algorithms |
| rdf:type |
owl:Thing yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment |
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. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal. (en) En théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d'un graphe de proche en proche à partir d'un sommet initial. Un cas particulier important est le parcours d'arbre. Le mot parcours est également utilisé dans un sens différent, comme synonyme de chemin (un parcours fermé étant un circuit). (fr) 그래프 트래버설(영어: Graph traversal)은 그래프의 모든 꼭짓점들을 방문하는 것과 관련한 문제와 그 방법을 말한다. 트리 순회는 그래프 순회의 특수한 경우이다. 트리 순회와 달리, 일반적인 그래프 순회에서는, 각 꼭짓점들을 한 번 이상 방문하는 경우도 있다. 다른 모든 꼭짓점들을 연결시켜주는 트리의 루트같은 꼭짓점이 존재하지 않을 수도 있다. (ko) У комп'ютерних науках, пошук по графу (або обхід графа) це процес проходження (перевірки або оновлення) кожної вершини графа. Такі алгоритми пошуку класифікують відповідно до порядку проходження вершин. Пошук по дереву є особливим випадком пошуку по графу. (uk) 图的遍历问题分为四类： * 遍历完所有的边而不能有重复，即所謂“欧拉路径问题”（又名一笔画问题）； * 遍历完所有的顶点而没有重复，即所谓“哈密頓路径问题”。 * 遍历完所有的边而可以有重复，即所谓“中国邮递员问题”； * 遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。 对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。 第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。 (zh) |
| rdfs:label |
Graph traversal (en) Parcours de graphe (fr) 그래프 순회 (ko) Пошук по графу (uk) 图的遍历 (zh) |
| owl:differentFrom |
dbr:Facebook_Graph_Search |
| owl:sameAs |
freebase:Graph traversal yago-res:Graph traversal wikidata:Graph traversal dbpedia-fa:Graph traversal dbpedia-fr:Graph traversal dbpedia-hu:Graph traversal dbpedia-ko:Graph traversal dbpedia-sr:Graph traversal dbpedia-uk:Graph traversal dbpedia-vi:Graph traversal dbpedia-zh:Graph traversal https://global.dbpedia.org/id/53uYT |
| prov:wasDerivedFrom |
wikipedia-en:Graph_traversal?oldid=1103034087&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Graph-scan.png |
| foaf:isPrimaryTopicOf |
wikipedia-en:Graph_traversal |
| is dbo:wikiPageDisambiguates of |
dbr:Traversal |
| is dbo:wikiPageRedirects of |
dbr:Graph_search dbr:Graph_exploration_algorithm dbr:Graph_search_algorithm dbr:Node_traversal |
| is dbo:wikiPageWikiLink of |
dbr:Propositional_calculus dbr:Algorithmic_technique dbr:Anytime_A* dbr:Deterministic_rendezvous_problem dbr:Shakey_the_robot dbr:Rooted_graph dbr:Glossary_of_artificial_intelligence dbr:Graph_Query_Language dbr:Graph_database dbr:Connected-component_labeling dbr:Computational_law dbr:Parallel_computing dbr:Micromouse dbr:Travelling_salesman_problem dbr:Tree_traversal dbr:Web_framework dbr:Graph_search dbr:A*_search_algorithm dbr:Directory-based_cache_coherence dbr:Flood_fill dbr:Graph_(abstract_data_type) dbr:Gremlin_(query_language) dbr:Stable_roommates_problem dbr:Symposium_on_Combinatorial_Search dbr:Traversal dbr:Graph_exploration_algorithm dbr:Graph_search_algorithm dbr:OpenSceneGraph dbr:Canadian_traveller_problem dbr:Search_algorithm dbr:External_memory_graph_traversal dbr:Recursive_join dbr:Polygonalization dbr:Node_traversal |
| is foaf:primaryTopic of |
wikipedia-en:Graph_traversal |
