| rdfs:comment
| - خوارزمية كروسكال (بالإنجليزية: Kruskal Algorithm) هي خوارزمية لإيجاد الطريق ذي الوزن الأقل أو الأقل كلفة، وهي خوارزمية شرهة في نظرية المخططات حيث تجد الطريق الأقل وزن لمخطط متصل موزون، بإضافة الكلفة في كل مرحلة، وهذا يعني أنها توجد المجموعات الجزئية التي تحتوي على الخط الواصل بين عقدتين الذي يكون الشجرة التي تحتوي على جميع العقد، حيث يتم تقليل المجموع الكلي لأوزان الخطوط الواصلة بين العقد في هذه الشجرة لأقل ما يمكن. إذا كان المخطط غير متصل سيقوم بإيجاد الشجرة التي تحتوي على اقل كلفة لكل شجرة في الغابة. ظهرت هذه الخوارزمية لأول مرة في وقائع المجتمع الأمريكي للرياضيين عام 1956 وكتبها . (ar)
- Kruskalův algoritmus (v České republice se někdy mylně zaměňuje s Borůvkovým algoritmem, ten ale funguje odlišně) je jeden z algoritmů využívaných v teorii grafů k nalezení minimální kostry grafu, jehož hrany mají nezáporné ohodnocení (délku). U souvislého grafu hledá podmnožinu hran, která tvoří strom obsahující všechny uzly, s tím, že celková váha (součet délek) hran grafu je minimální. V případě grafu o více komponentách, algoritmus hledá les minimálních koster, tedy minimální kostru každé komponenty. Kruskalův algoritmus je příkladem hladového algoritmu. (cs)
- El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada ). Este algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956..Otros algoritmos que sirven para hallar el árbol de expansión mínima o árbol recubridor mínimo son el algoritmo de Prim, el algoritmo del borrador inverso y el algoritmo de Boruvka. (es)
- En informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal. (fr)
- クラスカル法（英: Kruskal's algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。 (ja)
- 컴퓨터 과학에서 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 , 꼭짓점의 개수를 라고 하면 이 알고리즘은 의 시간복잡도를 가진다. (ko)
- Algorytm Kruskala – algorytm grafowy wyznaczający minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego. Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku w czasopiśmie Proceedings of the American Mathematical Society. (pl)
- Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм описан в 1956 году,этот алгоритм почти не отличается от алгоритма Борувки, предложенного в 1926 году. (ru)
- Kruskals algoritm är en girig algoritm för att skapa ett minimalt uppspännande träd från en godtycklig sammanhängande, viktad och oriktad graf. Algoritmen bygger en skog av träd som allt eftersom växer ihop. Algoritmen är girig, eftersom den hela tiden lägger till den kortaste kanten den kan hitta till sina delträd. (sv)
- Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графу. Алгоритм було вперше описано 1956 року. (uk)
- Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法和等。三種演算法都是贪心算法的應用。和Boruvka演算法不同的地方是，Kruskal演算法在圖中存在相同權值的邊時也有效。 (zh)
- En teoria de grafs, l'algorisme de Kruskal és un algorisme que serveix per trobar l'arbre generador amb el menor pes que connecta tots els punts d'un graf. Es tracta d'un algorisme voraç, ja que troba l'arbre generador mínim per un graf ponderat connex afegint arcs de pes superior en cada pas. Això significa que troba un subconjunt d'arestes que formen un arbre que inclou cada vèrtex, tal que el pes total de les arestes és el mínim. Si el graf no és connex troba un bosc generador mínim (un arbre generador mínim per a cada component connex). (ca)
- Der Algorithmus von Kruskal ist ein Greedy-Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu zusätzlich zusammenhängend, kantengewichtet und endlich sein. Der Algorithmus stammt von Joseph Kruskal, der ihn 1956 in der Zeitschrift „Proceedings of the American Mathematical Society“ veröffentlichte. Er beschrieb ihn dort wie folgt: Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet. (de)
- Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of all the edges in the tree is minimized. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.) It is a greedy algorithm in graph theory as in each step it adds the next lowest-weight edge that will not form a cycle to the minimum spanning forest. (en)
- L'algoritmo di Kruskal è un algoritmo ottimo utilizzato per calcolare gli alberi di supporto minimi di un grafo non orientato e con gli archi con costi non negativi. Prende il nome dal matematico americano Joseph Kruskal che lo ideò e propose nel 1956. Esempio dell'algoritmo di Kruskal su un grafo connesso, con i pesi basati sulla distanza euclidea. (it)
- Kruskals algoritme is een algoritme uit de grafentheorie om de minimaal opspannende boom te vinden voor gewogen grafen. Hierbij zoeken we een deelverzameling van bogen die een boom vormen die alle knopen bevat, waarbij daarenboven het totale gewicht minimaal is. Als de graaf niet volledig verbonden is dan zoekt het een minimaal opspannend woud (een minimale overspannende boom voor elke onverbonden deelgraaf). Kruskals algoritme, beschreven in 1956 is een voorbeeld van een . Het algoritme kan als volgt geformuleerd worden (G is de gegeven graaf): (nl)
- O algoritmo de Kruskal é um algoritmo em teoria dos grafos que busca uma árvore geradora mínima para um grafo conexo com pesos. Isto significa que ele encontra um subconjunto das arestas que forma uma árvore que inclui todos os vértices, onde o peso total, dado pela soma dos pesos das arestas da árvore, é minimizado. Se o grafo não for conexo, então ele encontra uma floresta geradora mínima (uma árvore geradora mínima para cada componente conexo do grafo). O algoritmo de Kruskal é um exemplo de um algoritmo guloso (também conhecido como ganancioso ou greedy). (pt)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)