This HTML5 document contains 248 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
n31https://meyavuz.wordpress.com/2017/03/10/
dbpedia-nohttp://no.dbpedia.org/resource/
dbpedia-svhttp://sv.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbrhttp://dbpedia.org/resource/
dbpedia-arhttp://ar.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
n22http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbpedia-mkhttp://mk.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-cshttp://cs.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n16http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-idhttp://id.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-huhttp://hu.dbpedia.org/resource/
dbpedia-skhttp://sk.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-thhttp://th.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-rohttp://ro.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbpedia-nlhttp://nl.dbpedia.org/resource/
goldhttp://purl.org/linguistics/gold/
yago-reshttp://yago-knowledge.org/resource/
n36https://global.dbpedia.org/id/
dbpedia-slhttp://sl.dbpedia.org/resource/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-kahttp://ka.dbpedia.org/resource/

Statements

Subject Item
dbr:Prim's_algorithm
rdf:type
yago:Algorithm105847438 yago:Abstraction100002137 dbo:Software yago:Procedure101023820 yago:Event100029378 yago:Activity100407535 yago:PsychologicalFeature100023100 yago:Rule105846932 yago:WikicatAlgorithms yago:YagoPermanentlyLocatedEntity yago:WikicatGraphAlgorithms yago:Act100030358
rdfs:label
Algorithmus von Prim Algoritme van Prim Prims algoritm Algorithme de Prim Algoritma Prim Algorytm Prima Algorisme de Prim 普林姆算法 Algoritmo de Prim Algoritmo de Prim 프림 알고리즘 プリム法 خوارزمية بريم Алгоритм Прима Jarníkův algoritmus Prim's algorithm Algoritmo di Prim Алгоритм Прима
rdfs:comment
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. 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. Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году. プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。 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. 普里姆算法（Prim's algorithm）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家发现；并在1957年由美国计算机科学家独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。 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. 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. 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. 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 까지 떨어진다. 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. Алгоритм Прима — жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графу. Побудова починається з дерева, що містить в собі одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить усі вершини початкового графу. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину, що не належить дереву. 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. في علوم الحاسوب، تعد خوارزمية بريم Prim's algorithm (المعروفة أيضًا باسم خوارزمية Jarník) هي خوارزمية جشعة تعثر على الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجه (weighted undirected graph). هذا يعني أنه يعثر على مجموعة فرعية من الحواف التي تشكل شجرة تتضمن كل رأس، حيث يجري تقليل الوزن الإجمالي لجميع حواف الشجرة إلى أدنى حد. تعمل الخوارزمية عن طريق بناء هذه الشجرة باستخدام رأسًا واحدًا في كل مرة، وتبدأ برأس عشوائية، في كل خطوة تضيف أرخص اتصال ممكن من الشجرة إلى رأس أخرى. 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. 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. 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. 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.
foaf:depiction
n22:Prim's_algorithm.svg n22:Prim's_algorithm_proof.svg n22:PrimAlgDemo.gif n22:Distributed_adjacency_matrix_for_parallel_prim.png
dcterms:subject
dbc:Graph_algorithms dbc:Greedy_algorithms dbc:Articles_with_example_pseudocode dbc:Articles_containing_proofs dbc:Articles_containing_video_clips dbc:Spanning_tree
dbo:wikiPageID
53783
dbo:wikiPageRevisionID
1122630917
dbo:wikiPageWikiLink
dbr:Parallel_algorithm dbr:Dense_graph dbr:Minimum_spanning_tree dbr:Connected_component_(graph_theory) dbr:Vertex_(graph_theory) n16:Prim's_algorithm.svg n16:Prim's_algorithm_proof.svg n16:PrimAlgDemo.gif dbc:Graph_algorithms dbr:Robert_C._Prim dbr:Vojtěch_Jarník dbc:Greedy_algorithms dbr:Graph_theory dbr:Undirected_graph n16:Distributed_adjacency_matrix_for_parallel_prim.png dbr:Big-O_notation dbr:D-ary_heap dbr:Linear_time dbr:Binary_heap dbc:Articles_with_example_pseudocode dbr:Weighted_graph dbc:Articles_containing_proofs dbc:Articles_containing_video_clips dbr:Distributed_minimum_spanning_tree dbr:Fibonacci_heap dbr:Reduction_Operator dbr:Asymptotic_computational_complexity dbr:Array_data_structure dbr:Dijkstra's_algorithm dbr:Sparse_graph dbr:Greedy_algorithm dbr:Greedoid dbr:Edge_(graph_theory) dbr:Borůvka's_algorithm dbr:Computer_science dbc:Spanning_tree n16:MAZE_30x20_Prim.ogv dbr:Shortest_path_problem dbr:Computer_scientist dbr:Pseudocode dbr:Flag_value dbr:Linked_list dbr:Time_complexity dbr:Czech_people dbr:Edsger_W._Dijkstra dbr:Kruskal's_algorithm dbr:Tree_(graph_theory) dbr:Adjacency_list dbr:Adjacency_matrix dbr:Priority_queue dbr:Broadcasting_(computing) dbr:Heap_(data_structure)
dbo:wikiPageExternalLink
n31:prims-algorithm-animation-for-randomly-distributed-points
owl:sameAs
freebase:m.0f2jn wikidata:Q470813 dbpedia-zh:普林姆算法 dbpedia-cs:Jarníkův_algoritmus dbpedia-fr:Algorithme_de_Prim dbpedia-nl:Algoritme_van_Prim dbpedia-sr:Примов_алгоритам dbpedia-ko:프림_알고리즘 dbpedia-sl:Primov_algoritem dbpedia-vi:Thuật_toán_Prim dbpedia-ka:პრიმის_ალგორითმი dbpedia-ca:Algorisme_de_Prim dbpedia-uk:Алгоритм_Прима dbpedia-ar:خوارزمية_بريم dbpedia-pt:Algoritmo_de_Prim dbpedia-ja:プリム法 dbpedia-mk:Примов_Алгоритам dbpedia-ro:Algoritmul_lui_Prim n36:4MhUQ dbpedia-fa:الگوریتم_پریم dbpedia-sk:Primov_algoritmus dbpedia-tr:Prim_algoritması dbpedia-es:Algoritmo_de_Prim dbpedia-th:ขั้นตอนวิธีของพริม yago-res:Prim's_algorithm dbpedia-hu:Prim-algoritmus dbpedia-it:Algoritmo_di_Prim dbpedia-sv:Prims_algoritm dbpedia-no:Prims_algoritme dbpedia-pl:Algorytm_Prima dbpedia-de:Algorithmus_von_Prim dbpedia-id:Algoritma_Prim dbpedia-he:האלגוריתם_של_פרים dbpedia-ru:Алгоритм_Прима
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Ordered_list dbt:Commons_category-inline dbt:Reflist
dbo:thumbnail
n22:PrimAlgDemo.gif?width=300
dbo:abstract
普里姆算法（Prim's algorithm）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家发现；并在1957年由美国计算机科学家独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。 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). Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году. プリム法とは、グラフ理論で重み付き連結グラフの最小全域木を求める最適化問題のアルゴリズムである。全域木（対象となるグラフの全頂点を含む辺の部分集合で構成される木）のうち、その辺群の重みの総和が最小となる木を求めるものである。このアルゴリズムは1930年に数学者 Vojtěch Jarník が発見し、1957年に計算機科学者ロバート・C・プリムが独自に発見、さらに1959年にはエドガー・ダイクストラが再発見しダイクストラ法の論文に記載している。そのため、DJP法、Jarník法、Prim-Jarník法などとも呼ばれることがある。アルゴリズムの発想や計算量は同時期に発表されたダイクストラ法に類似している。 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. 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. 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. 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. 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. في علوم الحاسوب، تعد خوارزمية بريم 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. تجد هذه الخوارزميات الحد الأدنى من مجموعة التفرعات الممتدة في رسم بياني محتمل غير متصل ؛ في المقابل، فإن الشكل الأساسي لخوارزمية بريم لا يجد سوى الحد الأدنى من الأشجار الممتدة في الرسوم البيانية المتصلة. ومع ذلك، عند تشغيل خوارزمية بريم بشكل منفصل لكل مكون متصل بالرسم البياني، يمكن أيضًا استخدامها للعثور على الحد الأدنى من مجموعة التفرعات الممتدة. من حيث تعقيدها الزمني المقارب، فإن هذه الخوارزميات الثلاثة متساوية في السرعة بالنسبة للرسوم البيانية المتفرقة، ولكنها أبطأ من الخوارزميات الأخرى الأكثر تعقيدًا. ومع ذلك، بالنسبة للرسوم البيانية الكثيفة بما فيه الكفاية، يمكن عمل خوارزمية بريم للعمل في الوقت الخطي، أو تلبية أو تحسين الحدود الزمنية للخوارزميات الأخرى. 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. Алгоритм Прима — жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графу. Побудова починається з дерева, що містить в собі одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить усі вершини початкового графу. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину, що не належить дереву. 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. 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. 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. 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. 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 까지 떨어진다. 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.
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Prim's_algorithm?oldid=1122630917&ns=0
dbo:wikiPageLength
18367
foaf:isPrimaryTopicOf
wikipedia-en:Prim's_algorithm
Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:List_of_examples_of_Stigler's_law
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:MENTOR_routing_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:1930_in_science
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:List_of_graph_theory_topics
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Reverse-delete_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:DJP_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:List_of_mathematical_proofs
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Jarnik
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Timeline_of_algorithms
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Kruskal's_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Priority_queue
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Maze_generation_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:1957_in_science
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:1959_in_science
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Distributed_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:DJP
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Heap_(data_structure)
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:D-ary_heap
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Euclidean_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Edmonds'_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:GrabCut
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Graph_theory
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Prim
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageDisambiguates
dbr:Prim's_algorithm
Subject Item
dbr:Rectilinear_minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Ishq_Kills
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Single-linkage_clustering
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Dijkstra's_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Borůvka's_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Greedoid
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Greedy_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Search_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Nearest-neighbor_chain_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Expected_linear_time_MST_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Robert_C._Prim
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Sorted_array
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Pairing_heap
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Parallel_algorithms_for_minimum_spanning_trees
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
Subject Item
dbr:Jarnik's_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Jarnik_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Jarniks_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Jarník's_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Jarník-Prim
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Jarník_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Jarníks_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prims_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prim’s_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prim-Jarnik
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prim-Jarnik's_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prim-Jarnik_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prim-Jarník
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prim-Jarník_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
dbr:Prim_algorithm
dbo:wikiPageWikiLink
dbr:Prim's_algorithm
dbo:wikiPageRedirects
dbr:Prim's_algorithm
Subject Item
wikipedia-en:Prim's_algorithm
foaf:primaryTopic
dbr:Prim's_algorithm