تا ۵۰٪ تخفیف در جشنواره کوله پشتی بهار
دیدن تخفیف‌ها و شرکت در جشنواره
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

الگوریتم پریم چیست؟ آموزش الگوریتم پریم در گراف

این صفحه عالی به معرفی الگوریتم پریم (Prim) و مقایسه پریم و کروسکال پرداخته و مثالی از الگوریتم پریم و پیاده‌سازی و پچیدگی زمانی الگوریتم پریم را بررسی کرده

الگوریتم پریم یک الگوریتم درخت پوشای کمینه است که یک گراف وزن‌دار را به‌عنوان ورودی می‌گیرد و زیرمجموعه یال‌های گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... آن را به‌گونه‌ای پیدا می‌کند که:

در سمت راست تصویر گراف و در سمت چپ عنوان "الگوریتم پریم نمایش داده شده است"

در این آموزش نحوه عملکرد الگوریتم پریم را خواهید آموخت؛ همچنین نمونه‌های کارکردی از الگوریتم پریم را در پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته، جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است، Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cاین مقاله عالی ابتدا توضیح می‌دهد که زبان برنامه نویسی c چیست، سپس به بررسی مزایا و معایب زبان C ، کاربردهای زبان سی ، و تفاوت بین C و ++C می‌پردازد و سی پلاس پلاسبرنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده خواهید دید.

الگوریتم پریم

این الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد در دسته‌ای از الگوریتم‌ها به‌نام الگوریتم‌های حریصانه قرار می‌گیرد که بهینه محلی را به امید یافتن یک بهینه جهانی پیدا می‌کنند. در الگوریتم پریم از یال‌هایی با کم‌ترین وزن شروع می‌کنیم و به اضافه کردن یال‌ها ادامه می‌دهیم تا به هدف خود برسیم.

مراحل پیاده سازی الگوریتم پریم به‌شرح زیر است:

مثالی از الگوریتم پریم

گراف وزن‌دار زیر را در نظر بگیرید:

 در این تصویر گرافی نمایش داده شده است که قصد داریم الگوریتم پریم را روی آن پیاده سازی کنیم

می‌خواهیم درخت پوشای کمینه این گراف را به‌دست آوریم (توجه کنید درخت پوشای کمینه در یک گراف لزوما یکتا نیست). یکی از رئوس گراف را برای شروع انتخاب می‌کنیم (در اینجا راس B را انتخاب کردیم).

 مرحله اول انجام الگوریتم پریم روی گراف وزن دار

یال با کم‌ترین وزن از این راس را انتخاب و به درخت اضافه می‌کنیم.

 مرحله دوم انجام الگوریتم پریم روی گراف وزن دار

کوتاه‌ترین یالی (یال با کم‌ترین وزن) که درخت فعلی را به یک راس جدید متصل می‌کند را پیدا می‌کنیم و به درخت اضافه می‌کنیم. این کار را تا زمانی که تمام رئوس گراف در درخت باشند ادامه می‌دهیم و به این صورت درخت پوشای کمینه را می‌سازیم.

مرحله چهارم انجام الگوریتم پریم روی گراف وزن دار
مرحله سوم انجام الگوریتم پریم روی گراف وزن دار
مرحله ششم انجام الگوریتم پریم روی گراف وزن دار
مرحله پنجم انجام الگوریتم پریم روی گراف وزن دار

نتیجه نهایی درخت پوشای کمینه‌ای است که با استفاده از الگوریتم پریم به‌دست آمده است.

پیاده‌سازی الگوریتم پریم

شبه کد الگوریتم پریم زیر نشان می‌دهد که چگونه دو مجموعه از رئوس U و V-U ایجاد می‌کنیم. مجموعه U شامل لیست رئوسی است که بازدید شده‌اند و در درخت قرار گرفته‌اند و مجموعه V-U لیست رئوسی است که بازدید نشده‌اند. رئوس را از مجموعه V-U به مجموعه U یک به یک با اتصال یال کم‌وزن منتقل می‌کنیم.

T = ∅;
U = { 1 };
while (U ≠ V)
    let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U;
    T = T ∪ {(u, v)}
    U = U ∪ {v}

در ادامه پیاده‌سازی الگوریتم پریم در زبان های برنامه نویسیزبان های برنامه نویسی چیست؟زبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مختلف آورده شده است. توجه کنید که در پیاده‌سازی‌های زیر ما با استفاده از ماتریس مجاورت، الگوریتم پریم را پیاده‌سازی کرده‌ایم ولی می‌توان این الگوریتم را با استفاده از لیست مجاورت هم پیاده‌سازی کرد.

Python

# Prim's Algorithm in Python


INF = 9999999
# number of vertices in graph
V = 5
# create a 2d array of size 5x5
# for adjacency matrix to represent graph
G = [[0, 9, 75, 0, 0],
     [9, 0, 95, 19, 42],
     [75, 95, 0, 51, 66],
     [0, 19, 51, 0, 31],
     [0, 42, 66, 31, 0]]
# create a array to track selected vertex
# selected will become true otherwise false
selected = [0, 0, 0, 0, 0]
# set number of edge to 0
no_edge = 0
# the number of egde in minimum spanning tree will be
# always less than(V - 1), where V is number of vertices in
# graph
# choose 0th vertex and make it true
selected[0] = True
# print for edge and weight
print("Edge : Weight\n")
while (no_edge < V - 1):
    # For every vertex in the set S, find the all adjacent vertices
    #, calculate the distance from the vertex selected at step 1.
    # if the vertex is already in the set S, discard it otherwise
    # choose another vertex nearest to selected vertex  at step 1.
    minimum = INF
    x = 0
    y = 0
    for i in range(V):
        if selected[i]:
            for j in range(V):
                if ((not selected[j]) and G[i][j]):  
                    # not in selected and there is an edge
                    if minimum > G[i][j]:
                        minimum = G[i][j]
                        x = i
                        y = j
    print(str(x) + "-" + str(y) + ":" + str(G[x][y]))
    selected[y] = True
    no_edge += 1

Java

// Prim's Algorithm in Java

import java.util.Arrays;

class PGraph {

  public void Prim(int G[][], int V) {

    int INF = 9999999;

    int no_edge; // number of edge

    // create a array to track selected vertex
    // selected will become true otherwise false
    boolean[] selected = new boolean[V];

    // set selected false initially
    Arrays.fill(selected, false);

    // set number of edge to 0
    no_edge = 0;

    // the number of egde in minimum spanning tree will be
    // always less than (V -1), where V is number of vertices in
    // graph

    // choose 0th vertex and make it true
    selected[0] = true;

    // print for edge and weight
    System.out.println("Edge : Weight");

    while (no_edge < V - 1) {
      // For every vertex in the set S, find the all adjacent vertices
      // , calculate the distance from the vertex selected at step 1.
      // if the vertex is already in the set S, discard it otherwise
      // choose another vertex nearest to selected vertex at step 1.

      int min = INF;
      int x = 0; // row number
      int y = 0; // col number

      for (int i = 0; i < V; i++) {
        if (selected[i] == true) {
          for (int j = 0; j < V; j++) { // not in selected and there is an edge if (!selected[j] && G[i][j] != 0) { if (min > G[i][j]) {
                min = G[i][j];
                x = i;
                y = j;
              }
            }
          }
        }
      }
      System.out.println(x + " - " + y + " :  " + G[x][y]);
      selected[y] = true;
      no_edge++;
    }
  }

  public static void main(String[] args) {
    PGraph g = new PGraph();

    // number of vertices in grapj
    int V = 5;

    // create a 2d array of size 5x5
    // for adjacency matrix to represent graph
    int[][] G = { { 0, 9, 75, 0, 0 }, { 9, 0, 95, 19, 42 }, { 75, 95, 0, 51, 66 }, { 0, 19, 51, 0, 31 },
        { 0, 42, 66, 31, 0 } };

    g.Prim(G, V);
  }
}

C

// Prim's Algorithm in C

#include<stdio.h>
#include<stdbool.h> 

#define INF 9999999

// number of vertices in graph
#define V 5

// create a 2d array of size 5x5
//for adjacency matrix to represent graph
int G[V][V] = {
  {0, 9, 75, 0, 0},
  {9, 0, 95, 19, 42},
  {75, 95, 0, 51, 66},
  {0, 19, 51, 0, 31},
  {0, 42, 66, 31, 0}};

int main() {
  int no_edge;  // number of edge

  // create a array to track selected vertex
  // selected will become true otherwise false
  int selected[V];

  // set selected false initially
  memset(selected, false, sizeof(selected));
  
  // set number of edge to 0
  no_edge = 0;

  // the number of egde in minimum spanning tree will be
  // always less than (V -1), where V is number of vertices in
  //graph

  // choose 0th vertex and make it true
  selected[0] = true;

  int x;  //  row number
  int y;  //  col number

  // print for edge and weight
  printf("Edge : Weight\n");

  while (no_edge < V - 1) {
    //For every vertex in the set S, find the all adjacent vertices
    // , calculate the distance from the vertex selected at step 1.
    // if the vertex is already in the set S, discard it otherwise
    //choose another vertex nearest to selected vertex  at step 1.

    int min = INF;
    x = 0;
    y = 0;

    for (int i = 0; i < V; i++) {
      if (selected[i]) {
        for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) {
              min = G[i][j];
              x = i;
              y = j;
            }
          }
        }
      }
    }
    printf("%d - %d : %d\n", x, y, G[x][y]);
    selected[y] = true;
    no_edge++;
  }

  return 0;
}

C++

// Prim's Algorithm in C++

#include <cstring>
#include <iostream>
using namespace std;

#define INF 9999999

// number of vertices in grapj
#define V 5

// create a 2d array of size 5x5
//for adjacency matrix to represent graph

int G[V][V] = {
  {0, 9, 75, 0, 0},
  {9, 0, 95, 19, 42},
  {75, 95, 0, 51, 66},
  {0, 19, 51, 0, 31},
  {0, 42, 66, 31, 0}};

int main() {
  int no_edge;  // number of edge

  // create a array to track selected vertex
  // selected will become true otherwise false
  int selected[V];

  // set selected false initially
  memset(selected, false, sizeof(selected));

  // set number of edge to 0
  no_edge = 0;

  // the number of egde in minimum spanning tree will be
  // always less than (V -1), where V is number of vertices in
  //graph

  // choose 0th vertex and make it true
  selected[0] = true;

  int x;  //  row number
  int y;  //  col number

  // print for edge and weight
  cout << "Edge"
     << " : "
     << "Weight";
  cout << endl;
  while (no_edge < V - 1) {
    //For every vertex in the set S, find the all adjacent vertices
    // , calculate the distance from the vertex selected at step 1.
    // if the vertex is already in the set S, discard it otherwise
    //choose another vertex nearest to selected vertex  at step 1.

    int min = INF;
    x = 0;
    y = 0;

    for (int i = 0; i < V; i++) {
      if (selected[i]) {
        for (int j = 0; j < V; j++) { if (!selected[j] && G[i][j]) { // not in selected and there is an edge if (min > G[i][j]) {
              min = G[i][j];
              x = i;
              y = j;
            }
          }
        }
      }
    }
    cout << x << " - " << y << " :  " << G[x][y];
    cout << endl;
    selected[y] = true;
    no_edge++;
  }

  return 0;
}

مقایسه الگوریتم پریم و کروسکال

الگوریتم کروسکال یکی دیگر از الگوریتم‌های محبوب درخت پوشای کمینه است که از منطق متفاوتی برای یافتن درخت پوشای کمینه یک گراف استفاده می‌کند. الگوریتم کروسکال به‌جای شروع از یک راس، تمام یال‌ها را از وزن کم به زیاد مرتب می‌کند و به اضافه کردن پایین‌ترین یال‌ها ادامه می‌دهد و یال‌هایی را که چرخه ایجاد می‌کنند نادیده می‌گیرد.

پیچیدگی زمانی الگوریتم پریم

پیچیدگی زمانی الگوریتم پریم از مرتبه O(E log V) است که E تعداد یال‌ها و V تعداد رئوس گراف را نشان می‌دهد.

کاربردهای الگوریتم پریم

از جمله کاربردهای الگوریتم پریم می‌توان به موارد زیر اشاره کرد:

جمع‌بندی

الگوریتم پریم یک تکنیک قدرتمند برای حل مسئله درخت پوشای کمینه در نظریه است. کارایی و مقیاس پذیری آن، آن را به ابزاری ارزشمند برای برنامه‌های کاربردی دنیای واقعی، از جمله طراحی شبکه، بهینه‌سازی لجستیک و تجزیه و تحلیل داده‌ها تبدیل می‌کند.

الگوریتم پریم چیست؟

الگوریتم Prim یک الگوریتم حریصانه است که برای یافتن درخت پوشای کمینه برای یک گراف استفاده می‌شود. این زیرمجموعه درختی را تشکیل می‌دهد که شامل هر رأس می‌شود و وزن کل تمام یال‌های درخت حداقل می‌باشد.

پیچیدگی الگوریتم پریم چیست؟

پیچیدگی زمانی الگوریتم پریم از مرتبه O(E log V) است که E تعداد یال‌ها و V تعداد رئوس گراف را نشان می‌دهد.

تفاوت الگوریتم پریم و کروسکال چیست؟

الگوریتم Prim راس ریشه را در ابتدا انتخاب می‌کند و سپس از راس به راس مجاور حرکت می‌کند. در سوی دیگر، الگوریتم Kruskal از یال با کم‌ترین وزن شروع کرده و یال‌های کم‌وزن بعدی را به درخت اضافه می‌کند.

الگوریتم پریم از چه رویکردی برای حل مسئله استفاده می‌کند؟

الگوریتم Prim برای یافتن درخت پوشای کمینه (مثل الگوریتم Kruskal) از رویکرد حریصانه استفاده می‌کند.

الگوریتم پریم بهتر است یا کروسکال؟

مزیت الگوریتم پریم پیچیدگی زمانی آن است که از الگوریتم کروسکال بهتر است؛ بنابراین الگوریتم پریم هنگام برخورد با گراف‌های متراکم که دارای یال‌های زیادی هستند مفید است؛ با این حال، الگوریتم پریم به ما اجازه نمی‌دهد تا کنترل زیادی روی یال‌های انتخاب شده، زمانی که چندین یال با وزن یکسان رخ می‌دهند، داشته باشیم.

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (2 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200