| dbo:abstract
|
- In computer science, Kosaraju-Sharir's algorithm (also known as Kosaraju's algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sharir. Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph. (en)
- En informatique, l'algorithme de Kosaraju est un algorithme de calcul des composantes fortement connexes d'un graphe orienté. Il effectue deux parcours en profondeur et a une complexité linéaire en la taille du graphe. (fr)
- 컴퓨터 과학에서 코사라주 알고리즘 (코사라주-샤리르 알고리즘으로도 알려져 있다.)은 유향그래프에서의 강한 연결 요소를 선형 시간에 찾는 알고리즘이다. 앨프리드 에이호, 존 홉크로프트 및 제프리 울만은 이 알고리즘을 및 의 것으로 보증한다. 는 1978년에 이 알고리즘을 제안하였지만 출판하지 않았고, 1981년 는 독자적으로 알고리즘을 발견하고 출판하였다. 이 알고리즘은 (모든 간선들의 방향을 뒤집은 그래프)가 원래 그래프와 정확히 같은 강한 연결 요소를 갖는다는 사실을 이용한다. (ko)
- Алгоритм Косараджу (в честь американского учёного индийского происхождения Самбасивы Рао Косараджу) — алгоритм поиска областей сильной связности в ориентированном графе. Чтобы найти области сильной связности, сначала выполняется поиск в глубину (DFS) на обращении исходного графа (то есть против дуг), вычисляя порядок выхода из вершин. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берём вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты. (ru)
- Kosaraju算法（也被称为Kosaraju–Sharir算法）是一个在线性时间内寻找一个有向图中的强连通分量的算法。阿尔佛雷德·艾侯，约翰·霍普克洛夫特和杰弗瑞·乌尔曼相信该算法来自于1978年撰写的一篇未发表论文之中。也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理：「一个图的反向图和原图具有一样的强连通分量」。 (zh)
- Алгоритм Косараджу (англ. kosaraju algorithm) — алгоритм для знаходження компонент сильної зв’язності орієнтованого графа. Ахо, Хопкрофт і Ульман приписують його до неоприлюдненого паперу від 1978. Він використовує факт, що транспонований граф (той самий граф з оберненими напрямками ребер) має ті самі компоненти сильної зв'язності, що й початковий граф. Алгоритм Косараджу працює так:
* Нехай G орієнтований граф і S порожній стек.
* Допоки S не містить всі вершини:
* Вибрати довільну вершину v не з S. Виконати пошук в глибину від v. По завершені пошуку в глибину для кожної вершини u, заштовхуємо u на S.
* Обернути всі ребра для отримання транспонованого графа.
* Доки S непорожній (містить вершину в порядку завершення, на верхівці стека — останнє завершення пошуку в глибину):
* Виштовхнути вершину v з S. Виконати пошук в глибину від v. Набір відвіданих вершин дасть компоненту сильної зв'язності, що містить v; записати це і видалити всі ці вершини з графа G і стека S. Так само можна використати пошук в ширину. (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8951 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In computer science, Kosaraju-Sharir's algorithm (also known as Kosaraju's algorithm) is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sharir. Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981. It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph. (en)
- En informatique, l'algorithme de Kosaraju est un algorithme de calcul des composantes fortement connexes d'un graphe orienté. Il effectue deux parcours en profondeur et a une complexité linéaire en la taille du graphe. (fr)
- 컴퓨터 과학에서 코사라주 알고리즘 (코사라주-샤리르 알고리즘으로도 알려져 있다.)은 유향그래프에서의 강한 연결 요소를 선형 시간에 찾는 알고리즘이다. 앨프리드 에이호, 존 홉크로프트 및 제프리 울만은 이 알고리즘을 및 의 것으로 보증한다. 는 1978년에 이 알고리즘을 제안하였지만 출판하지 않았고, 1981년 는 독자적으로 알고리즘을 발견하고 출판하였다. 이 알고리즘은 (모든 간선들의 방향을 뒤집은 그래프)가 원래 그래프와 정확히 같은 강한 연결 요소를 갖는다는 사실을 이용한다. (ko)
- Алгоритм Косараджу (в честь американского учёного индийского происхождения Самбасивы Рао Косараджу) — алгоритм поиска областей сильной связности в ориентированном графе. Чтобы найти области сильной связности, сначала выполняется поиск в глубину (DFS) на обращении исходного графа (то есть против дуг), вычисляя порядок выхода из вершин. Затем мы используем обращение этого порядка, чтобы выполнить поиск в глубину на исходном графе (в очередной раз берём вершину с максимальным номером, полученным при обратном проходе). Деревья в лесе DFS, которые выбираются в результате, представляют собой сильные компоненты. (ru)
- Kosaraju算法（也被称为Kosaraju–Sharir算法）是一个在线性时间内寻找一个有向图中的强连通分量的算法。阿尔佛雷德·艾侯，约翰·霍普克洛夫特和杰弗瑞·乌尔曼相信该算法来自于1978年撰写的一篇未发表论文之中。也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理：「一个图的反向图和原图具有一样的强连通分量」。 (zh)
- Алгоритм Косараджу (англ. kosaraju algorithm) — алгоритм для знаходження компонент сильної зв’язності орієнтованого графа. Ахо, Хопкрофт і Ульман приписують його до неоприлюдненого паперу від 1978. Він використовує факт, що транспонований граф (той самий граф з оберненими напрямками ребер) має ті самі компоненти сильної зв'язності, що й початковий граф. Алгоритм Косараджу працює так: (uk)
|
| rdfs:label
|
- Kosaraju's algorithm (en)
- Algorithme de Kosaraju (fr)
- Algoritmo di Kosaraju-Sharir (it)
- 코사라주 알고리즘 (ko)
- Алгоритм Косарайю (ru)
- Алгоритм Косараджу (uk)
- Kosaraju算法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
