Prim's algorithm
http://dbpedia.org/resource/Prim's_algorithm an entity of type: Software
Jarníkův algoritmus (v zahraničí známý jako Primův algoritmus) je v teorii grafů algoritmus hledající minimální kostru ohodnoceného grafu. Najde tedy takovou podmnožinu hran grafu, která tvoří strom obsahující všechny vrcholy původního grafu a součet ohodnocení hran z této množiny je minimální. Poprvé algoritmus popsal Vojtěch Jarník roku 1930, později byl znovuobjeven roku 1957 a poté ještě jednou roku 1959 Edsgerem Dijkstrou. V zahraničí se téměř výlučně používá označení Primův algoritmus, vzácně pak Jarníkův algoritmus nebo DJP algoritmus.
rdf:langString
Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er zunächst von Robert C. Prim und dann 1959 von Edsger W. Dijkstra wiederentdeckt. Daher wird der Algorithmus in der Literatur auch gelegentlich unter anderen Namen geführt, so etwa Prim-Dijkstra-Algorithmus oder Algorithmus von Jarnik, Prim und Dijkstra, im englischen Sprachraum auch Jarnik’s algorithm oder DJP algorithm.
rdf:langString
L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.
rdf:langString
プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。
rdf:langString
프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 까지 떨어진다.
rdf:langString
Het algoritme van Prim is een algoritme om de minimaal opspannende boom van een graaf te vinden. Het algoritme werd in 1930 ontdekt door de wiskundige en in 1957 onafhankelijk herontdekt door de informaticus . In 1959 werd het ook door Dijkstra ontdekt. Het algoritme wordt ook weleens het DJP-algoritme of algoritme van Jarnik genoemd.
rdf:langString
L'algoritmo di Prim è un algoritmo ottimo utilizzato in teoria dei grafi, informatica e ricerca operativa per determinare gli alberi di supporto minimi di un grafo non orientato e con pesi non negativi.
rdf:langString
Prims algoritm är en girig algoritm för att skapa ett minimalt uppspännande träd från en godtycklig sammanhängande, kostnadad och oriktad graf. Algoritmen finner i varje iteration den länk med lägst kostnad som kan förbinda trädet med en nod som ännu inte finns med i trädet, varpå trädet utökas med denna länk (och den nod som den ansluter till). Iterationen fortsätter så länge det finns noder som inte lagts till i trädet.
rdf:langString
Алгоритм Прима — жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графу. Побудова починається з дерева, що містить в собі одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить усі вершини початкового графу. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину, що не належить дереву.
rdf:langString
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.
rdf:langString
普里姆算法（Prim's algorithm）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家发现；并在1957年由美国计算机科学家独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
rdf:langString
في علوم الحاسوب، تعد خوارزمية بريم Prim's algorithm (المعروفة أيضًا باسم خوارزمية Jarník) هي خوارزمية جشعة تعثر على الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجه (weighted undirected graph). هذا يعني أنه يعثر على مجموعة فرعية من الحواف التي تشكل شجرة تتضمن كل رأس، حيث يجري تقليل الوزن الإجمالي لجميع حواف الشجرة إلى أدنى حد. تعمل الخوارزمية عن طريق بناء هذه الشجرة باستخدام رأسًا واحدًا في كل مرة، وتبدأ برأس عشوائية، في كل خطوة تضيف أرخص اتصال ممكن من الشجرة إلى رأس أخرى.
rdf:langString
En teoria de grafs, l'algorisme de Prim és un algorisme que serveix per trobar un arbre generador minimal en un graf connex, no dirigit i amb arestes etiquetades. En altres paraules, l'algorisme troba el subconjunt d'arestes que formen l'arbre amb tots els vèrtexs en què el pes total de les arestes de l'arbre és el mínim possible. Si el graf no és connex, llavors l'algorisme trobarà l'arbre generador mínim per a un dels components connexos del seu subgraf connex.
rdf:langString
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
rdf:langString
Algoritme Prim adalah sebuah algoritme dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung. Algoritme ini ditemukan pada 1930 oleh matematikawan dan kemudian secara terpisah oleh pada 1957 dan ditemukan kembali oleh Dijkstra pada 1959. Karena itu algoritme ini sering dinamai algoritme DJP atau algoritme Jarnik.
rdf:langString
In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
rdf:langString
Na ciência da computação o algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para encontrar uma árvore geradora mínima (minimal spanning tree) num grafo conectado, valorado e não direcionado. Isso significa que o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados. O algoritmo foi desenvolvido em 1930 pelo matemático Vojtěch Jarník e depois pelo cientista da computação Robert Clay Prim em 1957 e redescoberto por Edsger Dijkstra em 1959.
rdf:langString
Algorytm Prima – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR). Mając do dyspozycji graf nieskierowany i spójny, tzn. taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E′ zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E′ jest najmniejsza możliwa.
rdf:langString
rdf:langString
خوارزمية بريم
rdf:langString
Algorisme de Prim
rdf:langString
Jarníkův algoritmus
rdf:langString
Algorithmus von Prim
rdf:langString
Algoritmo de Prim
rdf:langString
Algoritma Prim
rdf:langString
Algorithme de Prim
rdf:langString
Algoritmo di Prim
rdf:langString
프림 알고리즘
rdf:langString
プリム法
rdf:langString
Algoritme van Prim
rdf:langString
Prim's algorithm
rdf:langString
Algorytm Prima
rdf:langString
Algoritmo de Prim
rdf:langString
Алгоритм Прима
rdf:langString
Prims algoritm
rdf:langString
Алгоритм Прима
rdf:langString
普林姆算法
xsd:integer
53783
xsd:integer
1122630917
rdf:langString
في علوم الحاسوب، تعد خوارزمية بريم Prim's algorithm (المعروفة أيضًا باسم خوارزمية Jarník) هي خوارزمية جشعة تعثر على الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجه (weighted undirected graph). هذا يعني أنه يعثر على مجموعة فرعية من الحواف التي تشكل شجرة تتضمن كل رأس، حيث يجري تقليل الوزن الإجمالي لجميع حواف الشجرة إلى أدنى حد. تعمل الخوارزمية عن طريق بناء هذه الشجرة باستخدام رأسًا واحدًا في كل مرة، وتبدأ برأس عشوائية، في كل خطوة تضيف أرخص اتصال ممكن من الشجرة إلى رأس أخرى. قام عالم الرياضيات التشيكي Vojtěch Jarník بتطوير الخوارزمية في عام 1930، ثم أعاد اكتشافها ونشرها من علماء الحاسوب Robert C. Prim في عام 1957 وEdsger W. Dijkstra في عام 1959. لذلك، يطلق عليها أحيانًا خوارزمية جارنيك، أو خوارزمية Prim – Jarník، أو خوارزمية Prim – Dijkstra أو خوارزمية DJP. تشمل الخوارزميات الأخرى المعروفة لهذه المشكلة خوارزمية Kruskal وخوارزمية Borůvka. تجد هذه الخوارزميات الحد الأدنى من مجموعة التفرعات الممتدة في رسم بياني محتمل غير متصل ؛ في المقابل، فإن الشكل الأساسي لخوارزمية بريم لا يجد سوى الحد الأدنى من الأشجار الممتدة في الرسوم البيانية المتصلة. ومع ذلك، عند تشغيل خوارزمية بريم بشكل منفصل لكل مكون متصل بالرسم البياني، يمكن أيضًا استخدامها للعثور على الحد الأدنى من مجموعة التفرعات الممتدة. من حيث تعقيدها الزمني المقارب، فإن هذه الخوارزميات الثلاثة متساوية في السرعة بالنسبة للرسوم البيانية المتفرقة، ولكنها أبطأ من الخوارزميات الأخرى الأكثر تعقيدًا. ومع ذلك، بالنسبة للرسوم البيانية الكثيفة بما فيه الكفاية، يمكن عمل خوارزمية بريم للعمل في الوقت الخطي، أو تلبية أو تحسين الحدود الزمنية للخوارزميات الأخرى.
rdf:langString
Jarníkův algoritmus (v zahraničí známý jako Primův algoritmus) je v teorii grafů algoritmus hledající minimální kostru ohodnoceného grafu. Najde tedy takovou podmnožinu hran grafu, která tvoří strom obsahující všechny vrcholy původního grafu a součet ohodnocení hran z této množiny je minimální. Poprvé algoritmus popsal Vojtěch Jarník roku 1930, později byl znovuobjeven roku 1957 a poté ještě jednou roku 1959 Edsgerem Dijkstrou. V zahraničí se téměř výlučně používá označení Primův algoritmus, vzácně pak Jarníkův algoritmus nebo DJP algoritmus.
rdf:langString
En teoria de grafs, l'algorisme de Prim és un algorisme que serveix per trobar un arbre generador minimal en un graf connex, no dirigit i amb arestes etiquetades. En altres paraules, l'algorisme troba el subconjunt d'arestes que formen l'arbre amb tots els vèrtexs en què el pes total de les arestes de l'arbre és el mínim possible. Si el graf no és connex, llavors l'algorisme trobarà l'arbre generador mínim per a un dels components connexos del seu subgraf connex. L'algorisme va ser dissenyat l'any 1930 pel matemàtic txec Vojtěch Jarník i posteriorment i de manera independent pel científic computacional Robert C. Prim el 1957 i redescobert per Edsger Dijkstra el 1959. Per aquesta raó, l'algorisme és també conegut com a algorisme DJP o algorisme de Jarnik.
rdf:langString
Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er zunächst von Robert C. Prim und dann 1959 von Edsger W. Dijkstra wiederentdeckt. Daher wird der Algorithmus in der Literatur auch gelegentlich unter anderen Namen geführt, so etwa Prim-Dijkstra-Algorithmus oder Algorithmus von Jarnik, Prim und Dijkstra, im englischen Sprachraum auch Jarnik’s algorithm oder DJP algorithm.
rdf:langString
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo. El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
rdf:langString
L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.
rdf:langString
In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959. Therefore, it is also sometimes called the Jarník's algorithm, Prim–Jarník algorithm, Prim–Dijkstra algorithmor the DJP algorithm. Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for each connected component of the graph, it can also be used to find the minimum spanning forest. In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms.However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.
rdf:langString
Algoritme Prim adalah sebuah algoritme dalam teori graf untuk mencari pohon rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung. Algoritme ini ditemukan pada 1930 oleh matematikawan dan kemudian secara terpisah oleh pada 1957 dan ditemukan kembali oleh Dijkstra pada 1959. Karena itu algoritme ini sering dinamai algoritme DJP atau algoritme Jarnik. Langkah-langkahnya adalah sebagai berikut:
* buat sebuah pohon yang terdiri dari satu node, dipilih secara acak dari graf
* buat sebuah himpunan yang berisi semua cabang di graf
* loop sampai semua cabang di dalam himpunan menghubungkan dua node di pohon
* hapus dari himpunan satu cabang dengan bobot terkecil yang menghubungkan satu node di pohon dengan satu node di luar pohon
* hubungkan cabang tersebut ke pohon Dengan struktur data sederhana, algoritme Prim dapat ditunjukkan berjalan dalam waktu (Elog V), di mana E adalah jumlah cabang dan V adalah jumlah node. Dengan , hal ini dapat ditekan menjadi O(E + Vlog V), yang jauh lebih cepat bila grafnya cukup padat sehingga E adalah (Vlog V).
rdf:langString
プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。
rdf:langString
프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 까지 떨어진다.
rdf:langString
Het algoritme van Prim is een algoritme om de minimaal opspannende boom van een graaf te vinden. Het algoritme werd in 1930 ontdekt door de wiskundige en in 1957 onafhankelijk herontdekt door de informaticus . In 1959 werd het ook door Dijkstra ontdekt. Het algoritme wordt ook weleens het DJP-algoritme of algoritme van Jarnik genoemd.
rdf:langString
L'algoritmo di Prim è un algoritmo ottimo utilizzato in teoria dei grafi, informatica e ricerca operativa per determinare gli alberi di supporto minimi di un grafo non orientato e con pesi non negativi.
rdf:langString
Prims algoritm är en girig algoritm för att skapa ett minimalt uppspännande träd från en godtycklig sammanhängande, kostnadad och oriktad graf. Algoritmen finner i varje iteration den länk med lägst kostnad som kan förbinda trädet med en nod som ännu inte finns med i trädet, varpå trädet utökas med denna länk (och den nod som den ansluter till). Iterationen fortsätter så länge det finns noder som inte lagts till i trädet.
rdf:langString
Algorytm Prima – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR). Mając do dyspozycji graf nieskierowany i spójny, tzn. taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E′ zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E′ jest najmniejsza możliwa. Algorytm został wynaleziony w 1930 przez czeskiego matematyka , a następnie odkryty na nowo przez informatyka w 1957 oraz niezależnie przez Edsgera Dijkstrę w 1959. Z tego powodu algorytm nazywany jest również czasami algorytmem Dijkstry-Prima, algorytmem DJP, algorytmem Jarníka, albo algorytmem Prima-Jarníka.
rdf:langString
Na ciência da computação o algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para encontrar uma árvore geradora mínima (minimal spanning tree) num grafo conectado, valorado e não direcionado. Isso significa que o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados. O algoritmo foi desenvolvido em 1930 pelo matemático Vojtěch Jarník e depois pelo cientista da computação Robert Clay Prim em 1957 e redescoberto por Edsger Dijkstra em 1959. Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o algoritmo de Kruskal e algoritmo de Boruvka, sendo que este último pode ser empregado em grafos desconexos, enquanto o algoritmo de Prim e o Algoritmo de Kruskal precisam de um grafo conexo.
rdf:langString
Алгоритм Прима — жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графу. Побудова починається з дерева, що містить в собі одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить усі вершини початкового графу. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину, що не належить дереву.
rdf:langString
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.
rdf:langString
普里姆算法（Prim's algorithm）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家发现；并在1957年由美国计算机科学家独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
xsd:nonNegativeInteger
18367
