Kruskal's algorithm
http://dbpedia.org/resource/Kruskal's_algorithm an entity of type: Software
خوارزمية كروسكال (بالإنجليزية: Kruskal Algorithm) هي خوارزمية لإيجاد الطريق ذي الوزن الأقل أو الأقل كلفة، وهي خوارزمية شرهة في نظرية المخططات حيث تجد الطريق الأقل وزن لمخطط متصل موزون، بإضافة الكلفة في كل مرحلة، وهذا يعني أنها توجد المجموعات الجزئية التي تحتوي على الخط الواصل بين عقدتين الذي يكون الشجرة التي تحتوي على جميع العقد، حيث يتم تقليل المجموع الكلي لأوزان الخطوط الواصلة بين العقد في هذه الشجرة لأقل ما يمكن. إذا كان المخطط غير متصل سيقوم بإيجاد الشجرة التي تحتوي على اقل كلفة لكل شجرة في الغابة. ظهرت هذه الخوارزمية لأول مرة في وقائع المجتمع الأمريكي للرياضيين عام 1956 وكتبها .
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
クラスカル法（英: Kruskal's algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。
rdf:langString
컴퓨터 과학에서 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 , 꼭짓점의 개수를 라고 하면 이 알고리즘은 의 시간복잡도를 가진다.
rdf:langString
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.
rdf:langString
Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм описан в 1956 году,этот алгоритм почти не отличается от алгоритма Борувки, предложенного в 1926 году.
rdf:langString
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.
rdf:langString
Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графу. Алгоритм було вперше описано 1956 року.
rdf:langString
Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法和等。三種演算法都是贪心算法的應用。和Boruvka演算法不同的地方是，Kruskal演算法在圖中存在相同權值的邊時也有效。
rdf:langString
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).
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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):
rdf:langString
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).
rdf:langString
rdf:langString
خوارزمية كروسكال
rdf:langString
Algorisme de Kruskal
rdf:langString
Kruskalův algoritmus
rdf:langString
Algorithmus von Kruskal
rdf:langString
Algoritmo de Kruskal
rdf:langString
Algoritmo di Kruskal
rdf:langString
Algorithme de Kruskal
rdf:langString
Kruskal's algorithm
rdf:langString
크러스컬 알고리즘
rdf:langString
クラスカル法
rdf:langString
Kruskals algoritme
rdf:langString
Algorytm Kruskala
rdf:langString
Algoritmo de Kruskal
rdf:langString
Алгоритм Краскала
rdf:langString
Kruskals algoritm
rdf:langString
克鲁斯克尔演算法
rdf:langString
Алгоритм Крускала
xsd:integer
53776
xsd:integer
1091274413
rdf:langString
خوارزمية كروسكال (بالإنجليزية: Kruskal Algorithm) هي خوارزمية لإيجاد الطريق ذي الوزن الأقل أو الأقل كلفة، وهي خوارزمية شرهة في نظرية المخططات حيث تجد الطريق الأقل وزن لمخطط متصل موزون، بإضافة الكلفة في كل مرحلة، وهذا يعني أنها توجد المجموعات الجزئية التي تحتوي على الخط الواصل بين عقدتين الذي يكون الشجرة التي تحتوي على جميع العقد، حيث يتم تقليل المجموع الكلي لأوزان الخطوط الواصلة بين العقد في هذه الشجرة لأقل ما يمكن. إذا كان المخطط غير متصل سيقوم بإيجاد الشجرة التي تحتوي على اقل كلفة لكل شجرة في الغابة. ظهرت هذه الخوارزمية لأول مرة في وقائع المجتمع الأمريكي للرياضيين عام 1956 وكتبها .
rdf:langString
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). Aquest algorisme va aparèixer per primer cop a Proceedings of the American Mathematical Society, pp. 48–50 el 1956 i va ser escrit per Joseph Kruskal. Altres algorismes per aquest problema poden ser l'algorisme de Prim, l'algorisme d'eliminació cap enrere o l'algorisme de Borůvka.
rdf:langString
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.
rdf:langString
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. Die kürzeste Kante bezeichnet dabei jeweils die Kante mit dem kleinsten Kantengewicht. Nach Abschluss des Algorithmus bilden die ausgewählten Kanten einen minimalen Spannbaum des Graphen. Wendet man den Algorithmus auf unzusammenhängende Graphen an, so berechnet er für jede Zusammenhangskomponente des Graphen einen minimalen Spannbaum. Diese Bäume bilden einen minimalen aufspannenden Wald.
rdf:langString
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. This algorithm first appeared in Proceedings of the American Mathematical Society, pp. 48–50 in 1956, and was written by Joseph Kruskal. It was rediscovered by . Other algorithms for this problem include Prim's algorithm, the reverse-delete algorithm, and Borůvka's algorithm.
rdf:langString
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.
rdf:langString
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.
rdf:langString
クラスカル法（英: Kruskal's algorithm）は、グラフ理論において重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。
rdf:langString
컴퓨터 과학에서 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 트리를 찾는 알고리즘이다. 변의 개수를 , 꼭짓점의 개수를 라고 하면 이 알고리즘은 의 시간복잡도를 가진다.
rdf:langString
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): "Voer de volgende stap zo vaak uit als mogelijk: Kies uit de bogen van G die nog niet werden gekozen, de kortste boog die geen kring vormt met de bogen die reeds werden gekozen." Met "kortste boog" bedoelt men de boog met het kleinste gewicht. Als er geen kandidaten meer overblijven vormen de geselecteerde bogen de minimaal opspannende boom.
rdf:langString
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.
rdf:langString
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. Si consideri un grafo non orientato e connesso dove V rappresenta il numero di vertici (o nodi) ed E il numero di spigoli (o archi). Ad ogni spigolo è associato un peso (o distanza): lo scopo dell'algoritmo è quello di trovare un albero ricoprente di peso minimo, cioè quello in cui la somma dei pesi sia minima. L'algoritmo può essere applicato solo se si dispone di due o più vertici. L'algoritmo di Kruskal si basa sulla seguente semplice idea: ordiniamo gli archi in ordine crescente di costo e successivamente li analizziamo singolarmente, inserendo l'arco nella soluzione se non forma cicli con gli archi precedentemente selezionati. Notiamo che ad ogni passo, se abbiamo più archi con lo stesso costo, è indifferente quale viene scelto. Esempio dell'algoritmo di Kruskal su un grafo connesso, con i pesi basati sulla distanza euclidea.
rdf:langString
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). Seu funcionamento é mostrado a seguir:
* crie uma floresta F (um conjunto de árvores), onde cada vértice no grafo é uma árvore separada
* crie um conjunto S contendo todas as arestas do grafo
* enquanto S for não-vazio, faça:
* remova uma aresta com peso mínimo de S
* se essa aresta conecta duas árvores diferentes, adicione-a à floresta, combinando duas árvores numa única árvore parcial
* do contrário, descarte a aresta Ao fim do algoritmo, a floresta tem apenas um componente e forma uma árvore geradora mínima do grafo. Com o uso de uma estrutura de dados eficiente, o algoritmo de Kruskal possui complexidade de tempo igual a O (m log n), onde m representa o número de arestas e n o número de vértices.
rdf:langString
Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм описан в 1956 году,этот алгоритм почти не отличается от алгоритма Борувки, предложенного в 1926 году.
rdf:langString
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.
rdf:langString
Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графу. Алгоритм було вперше описано 1956 року.
rdf:langString
Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法和等。三種演算法都是贪心算法的應用。和Boruvka演算法不同的地方是，Kruskal演算法在圖中存在相同權值的邊時也有效。
xsd:nonNegativeInteger
15208
