برنامه مسیر ۸ ماهه تا کنکور: مشاوره خصوصیت با استاد رضوی رو رزرو کن!
رزرو مشاوره
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

ماتریس مجاورت، آموزش ماتریس مجاورت گراف

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

در نظریه گرافهمه چیز در مورد نظریه گراف (Graph Theory)همه چیز در مورد نظریه گراف (Graph Theory)در این مقاله یک مقدمه جامع در رابطه با نظریه گراف ارائه شده است و سعی شده نشان داده شود که دانستن برخی از مبانی نظریه گراف تا چه میزان می­‌تواند مفید و موثر باشد.، ماتریس مجاورت روشی برای توصیف ساختار گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... متناهی است. این ماتریس، دو بعدی است و برای ترسیم ارتباط بین گره‌های گراف استفاده می‌شود.

نمایش گراف

در حالت کلی دو روش رایج برای نشان دادن یک گراف وجود دارد:

ماتریس مجاورت

یک ماتریس مجاورت یک گراف را به عنوان ماتریس بولی (0 و 1) نشان می‌دهد.

لیست مجاورت

در این روش، آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100آموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه ای از لیست ها برای ذخیره یال‌های بین دو راس استفاده می‌شود. اندازه آرایه برابر با تعداد رئوس (یعنی n) است. هر شاخص در این آرایه نشان‌دهنده یک راس خاص در نمودار است. ورودی در فهرست i آرایه حاوی یک لیست پیوندیلیست پیوندی چیست؟ آموزش لیست پیوندی ساده، دو طرفه و حلقویلیست پیوندی چیست؟ آموزش لیست پیوندی ساده، دو طرفه و حلقویلیست پیوندی چیست؟ این صفحه عالی به آموزش لیست پیوندی ساده، دو طرفه و حلقوی با مثال پرداخته و پیاده سازی و عملیات مهم و کاربردهای لیست پیوندی را گفته است حاوی رئوس مجاور راس i است. در این مقاله ما به نحوه نمایش گراف با ماتریس مجاورت می‌پردازیم.

ساختار ماتریس مجاورت

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

به عنوان مثال، گراف زیر را در نظر بگیرید:

گراف مجاورت

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

جدول مجاورت

هر سلول در جدول/ماتریس بالا به صورت Aij نشان داده می‌شود که i و j رئوس هستند. مقدار Aij یا 1 یا 0 است، بسته به اینکه آیا یک یال از راس i تا راس j وجود دارد.

اگر یالی از i به j وجود داشته باشد، مقدار Aij یک است؛ درغیراین صورت صفر است. برای مثال، یک یال از راس 1 به راس 2 وجود دارد، بنابراین A12  یک است و هیچ یالی از راس 1 تا 3 وجود ندارد، همچنین A13 صفر است. در گراف‌های بدون جهت، ماتریس نسبت به قطر متقارن است.

پیاده‌ سازی

در ادامه به پیاده‌ سازی ماتریس مجاورت با زبان های برنامه نویسیزبان های برنامه نویسی چیست؟زبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مانند پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (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 می‌پردازد می‌پردازیم:

Python

class Graph(object):
    # Initialize the matrix
    def __init__(self, size):
        self.adjMatrix = []
        for i in range(size):
            self.adjMatrix.append([0 for i in range(size)])
        self.size = size

    # Add edges
    def add_edge(self, v1, v2):
        if v1 == v2:
            print("Same vertex %d and %d" % (v1, v2))
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1

    # Remove edges
    def remove_edge(self, v1, v2):
        if self.adjMatrix[v1][v2] == 0:
            print("No edge between %d and %d" % (v1, v2))
            return
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0

    def __len__(self):
        return self.size

    # Print the matrix
    def print_matrix(self):
        for row in self.adjMatrix:
            for val in row:
                print("{:4}".format(val)),
            print

def main():
    g = Graph(5)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)

    g.print_matrix()

if __name__ == "__main__":
    main()

Java

public class Graph {
  private boolean adjMatrix[][];
  private int numVertices;

  // Initialize the matrix
  public Graph(int numVertices) {
    this.numVertices = numVertices;
    adjMatrix = new boolean[numVertices][numVertices];
  }

  // Add edges
  public void addEdge(int i, int j) {
    adjMatrix[i][j] = true;
    adjMatrix[j][i] = true;
  }

  // Remove edges
  public void removeEdge(int i, int j) {
    adjMatrix[i][j] = false;
    adjMatrix[j][i] = false;
  }

  // Print the matrix
  public String toString() {
    StringBuilder s = new StringBuilder();
    for (int i = 0; i  numVertices; i++) {
      s.append(i + ": ");
      for (boolean j : adjMatrix[i]) {
        s.append((j ? 1 : 0) + " ");
      }
      s.append("\n");
    }
    return s.toString();
  }

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

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);

    System.out.print(g.toString());
  }
}

C++

#include 
using namespace std;

class Graph
{
private:
    bool **adjMatrix;
    int numVertices;

public:
    // Initialize the matrix to zero
    Graph(int numVertices)
    {
        this->numVertices = numVertices;
        adjMatrix = new bool *[numVertices];
        for (int i = 0; i  numVertices; i++)
        {
            adjMatrix[i] = new bool[numVertices];
            for (int j = 0; j  numVertices; j++)
                adjMatrix[i][j] = false;
        }
    }

    // Add edges
    void addEdge(int i, int j)
    {
        adjMatrix[i][j] = true;
        adjMatrix[j][i] = true;
    }

    // Remove edges
    void removeEdge(int i, int j)
    {
        adjMatrix[i][j] = false;
        adjMatrix[j][i] = false;
    }

    // Print the martix
    void toString()
    {
        for (int i = 0; i  numVertices; i++)
        {
            cout  i  " : ";
            for (int j = 0; j  numVertices; j++)
                cout  adjMatrix[i][j]  " ";
            cout  "\n";
        }
    }

    ~Graph()
    {
        for (int i = 0; i  numVertices; i++)
            delete[] adjMatrix[i];
        delete[] adjMatrix;
    }
};

int main()
{
    Graph g(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);

    g.toString();
}

C

// Adjacency Matrix representation in C

#include 
#define V 4

// Initialize the matrix to zero
void init(int arr[][V])
{
    int i, j;
    for (i = 0; i  V; i++)
        for (j = 0; j  V; j++)
            arr[i][j] = 0;
}

// Add edges
void addEdge(int arr[][V], int i, int j)
{
    arr[i][j] = 1;
    arr[j][i] = 1;
}

// Print the matrix
void printAdjMatrix(int arr[][V])
{
    int i, j;

    for (i = 0; i  V; i++)
    {
        printf("%d: ", i);
        for (j = 0; j  V; j++)
        {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int adjMatrix[V][V];

    init(adjMatrix);
    addEdge(adjMatrix, 0, 1);
    addEdge(adjMatrix, 0, 2);
    addEdge(adjMatrix, 1, 2);
    addEdge(adjMatrix, 2, 0);
    addEdge(adjMatrix, 2, 3);

    printAdjMatrix(adjMatrix);

    return 0;
}

مزایا و معایب ماتریس مجاورت

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

مزایا

معایب

کاربردها

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

جمع‌بندی

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

ماتریس مجاورت چیست؟

در نظریه گراف و علوم کامپیوتر، ماتریس مجاورت یک ماتریس مربعی است که یک گراف متناهی را نشان می‌دهد. عناصر ماتریس نشان می‌دهد که آیا جفت رئوس در گراف مجاور هستند یا نه. در یک گراف ساده متناهی، ماتریس مجاورت یک ماتریس (0،1) با صفر در قطر آن است.

چه زمانی باید از ماتریس مجاورت استفاده کرد؟

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

مهم‌ترین عیب ماتریس مجاورت چیست؟

مهم‌ترین نقطه ضعف نمایش ماتریس مجاورت این است که به ذخیره‌سازی از مرتبه زمانی n2 نیاز دارد، حتی اگر گراف به اندازه O(n) یال داشته باشد.

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