| dbo:abstract
|
- Der Algorithmus von Tarjan (nach seinem Erfinder Robert Tarjan) dient in der Graphentheorie zur Bestimmung der starken Zusammenhangskomponenten (SZKn) eines gerichteten Graphen. (de)
- En théorie des graphes, l'algorithme de Tarjan permet de déterminer les composantes fortement connexes d'un graphe orienté. Il porte le nom de son inventeur, Robert Tarjan. L'algorithme de Tarjan est de complexité linéaire, comme l'algorithme de Kosaraju, mais a l'avantage de ne faire qu'une passe sur le graphe au lieu de deux. (fr)
- Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. The algorithm is named for its inventor, Robert Tarjan. (en)
- L'algoritmo di Tarjan, così chiamato per il nome del suo inventore Robert Tarjan, è un algoritmo usato nella teoria dei grafi per trovare le componenti fortemente connesse di un grafo. Un'applicazione tipica dell'algoritmo è la ricerca dei cicli. Ha la stessa efficienza dell'. (it)
- Tarjan算法 （以發現者Robert Tarjan命名）是一個在圖中尋找強連通分量的算法。雖然發表時間更早，它仍可以被視為Kosaraju算法的一個改進。它的效率跟差不多。 (zh)
- Алгоритм Тар'яна — алгоритм пошуку компонент сильної зв'язності в орієнтованому графі, що працює за лінійний час. Цей алгоритм ґрунтується на тому, що: 1.
* Вершини розглядаються у зворотному топологічному порядку, тому в кінці рекурсивної функції для початкової вершини не зустрінеться жодна вершина з тієї ж сильної компоненти, оскільки всі вершини, досяжні з початкової, вже опрацьовано. 2.
* Зворотні зв'язки в дереві дають інший шлях з однієї вершини в іншу і зв'язують сильні компоненти. (uk)
- Алгоритм Тарьяна — алгоритм поиска компонент сильной связности в орграфе, работающий за линейное время. Этот алгоритм основан на том, что: 1.
* Вершины рассматриваются в обратном топологическом порядке, поэтому в конце рекурсивной функции для исходной вершины не будет встречено ни одной вершины из той же компоненты сильной связности, так как все вершины, достижимые из исходной, уже обработаны. 2.
* Обратные связи в дереве дают второй путь из одной вершины в другую и связывают компоненты сильной связности в одну. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12318 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:caption
|
- Tarjan's algorithm animation (en)
|
| dbp:data
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Der Algorithmus von Tarjan (nach seinem Erfinder Robert Tarjan) dient in der Graphentheorie zur Bestimmung der starken Zusammenhangskomponenten (SZKn) eines gerichteten Graphen. (de)
- En théorie des graphes, l'algorithme de Tarjan permet de déterminer les composantes fortement connexes d'un graphe orienté. Il porte le nom de son inventeur, Robert Tarjan. L'algorithme de Tarjan est de complexité linéaire, comme l'algorithme de Kosaraju, mais a l'avantage de ne faire qu'une passe sur le graphe au lieu de deux. (fr)
- Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. The algorithm is named for its inventor, Robert Tarjan. (en)
- L'algoritmo di Tarjan, così chiamato per il nome del suo inventore Robert Tarjan, è un algoritmo usato nella teoria dei grafi per trovare le componenti fortemente connesse di un grafo. Un'applicazione tipica dell'algoritmo è la ricerca dei cicli. Ha la stessa efficienza dell'. (it)
- Tarjan算法 （以發現者Robert Tarjan命名）是一個在圖中尋找強連通分量的算法。雖然發表時間更早，它仍可以被視為Kosaraju算法的一個改進。它的效率跟差不多。 (zh)
- Алгоритм Тар'яна — алгоритм пошуку компонент сильної зв'язності в орієнтованому графі, що працює за лінійний час. Цей алгоритм ґрунтується на тому, що: 1.
* Вершини розглядаються у зворотному топологічному порядку, тому в кінці рекурсивної функції для початкової вершини не зустрінеться жодна вершина з тієї ж сильної компоненти, оскільки всі вершини, досяжні з початкової, вже опрацьовано. 2.
* Зворотні зв'язки в дереві дають інший шлях з однієї вершини в іншу і зв'язують сильні компоненти. (uk)
- Алгоритм Тарьяна — алгоритм поиска компонент сильной связности в орграфе, работающий за линейное время. Этот алгоритм основан на том, что: 1.
* Вершины рассматриваются в обратном топологическом порядке, поэтому в конце рекурсивной функции для исходной вершины не будет встречено ни одной вершины из той же компоненты сильной связности, так как все вершины, достижимые из исходной, уже обработаны. 2.
* Обратные связи в дереве дают второй путь из одной вершины в другую и связывают компоненты сильной связности в одну. (ru)
|
| rdfs:label
|
- Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten (de)
- Algoritmo di Tarjan per le componenti fortemente connesse (it)
- Algorithme de Tarjan (fr)
- Tarjan's strongly connected components algorithm (en)
- Алгоритм Тарьяна (ru)
- Tarjan算法 (zh)
- Алгоритм Тар'яна (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is owl:differentFrom
of | |
| is foaf:primaryTopic
of | |
