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

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

نمایش گراف

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

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

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

لیست مجاورت

در این روش، آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 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 وجود دارد، بنابراین A₁₂یکاست و هیچ یالی از راس 1 تا 3 وجود ندارد، همچنین A₁₃صفر است. در گراف‌های بدون جهت، ماتریس نسبت به قطر متقارن است.

پیاده‌ سازی

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()

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());
  }
}

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();
}

#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;
}

// 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;
}

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

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

مزایا

عملیات اساسی مانند اضافه کردن یک یال، حذف یک یال و بررسی اینکه آیا یک یال از راس i به راس j وجود دارد، از مرتبه زمانی ثابت و بسیار بهینه است.
اگر گراف متراکم و تعداد یال‌ها زیاد باشد، یک ماتریس مجاورت باید اولین انتخاب باشد حتی اگر گراف و ماتریس مجاورت پراکنده باشند، می‌توانیم آن‌ها را با استفاده از ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است هایی که برای ماتریس‌های پراکنده مناسب‌اند نشان دهیم.
پیشرفت‌های اخیر در سخت افزارسخت افزار چیست - بررسی اجزای اصلی سخت افزار کامپیوتردر این صفحه بررسی شده که سخت افزار چیست و سخت افزار کامپیوتر به زبان ساده معرفی شده است، همچنین به بررسی اجزای اصلی سخت افزار کامپیوتر پرداخته شده است ما را قادر می‌سازد تا عملیات‌های ماتریسی زمانبر را بر روی پردازنده گرافیکی (GPU)پردازنده گرافیکی (GPU) چیست؟ بررسی انواع، وظایف و کاربردهادر این مقاله به تاریخچه پردازنده گرافیکی، علت به وجود آمدن آن، انواع GPUها و همچنین مزایا و معایب هر یک متناسب با نیاز کاربران پرداخته‌ شده است انجام دهیم.
با انجام عملیات روی ماتریس مجاورت، می‌توانیم بینش‌های مهمی در مورد ماهیت گراف و رابطه بین رئوس آن بدست آوریم.

معایب

فضای مورد نیاز VxV ماتریس مجاورت، باعث می‌شود که از نظر حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتردر این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم بهینه نباشد. گراف‌های موجود در طبیعت معمولاً اتصالات زیادی ندارند، به همین دلیل است که لیست های مجاورت برای اکثر موارد انتخاب بهتری هستند.
در مورد استفاده از فضا برای گراف‌های پراکنده ناکارآمد است زیرا فضای O(N²) را اشغال می‌کند.
محاسبه همه همسایگان یک راس، زمان O(N) دارد.

حتما بخوانید :

ماتریس در ساختمان داده⚡️معرفی انواع ماتریس (خلوت،قطری)

کاربردها

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

الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد های گراف: بسیاری از الگوریتم‌های گراف، مانند الگوریتم‌ الگوریتم فلوید وارشالالگوریتم فلوید وارشال چیست، آموزش الگوریتم فلوید وارشالالگوریتم فلوید وارشال چیست، این صفحه عالی به بررسی و آموزش الگوریتم فلوید وارشال با مثال پرداخته و نحوه پیاده سازی الگوریتم فلوید وارشال و پیچیدگی آن را گفته و الگوریتم کروسکالالگوریتم کراسکال یا کروسکال⚡️مثال+پیاده سازی+پیچیدگی زمانیاین صفحه عالی به معرفی الگوریتم کراسکال یا کروسکال (Kruskal) پرداخته و مثالی از الگوریتم کروسکال و پیاده‌سازی و پچیدگی زمانی الگوریتم کروسکال را بررسی کرده ،‌ از ماتریس‌ های مجاورت برای نمایش نمودارها استفاده می‌کنند.
پردازش تصویرپردازش تصویر دیجیتال چیست؟ چه انواعی دارد؟ چه مراحلی را شامل می‌شود؟ پردازش تصویر یکی از فیلدهای پرطرفدار مرتبط با گرافیک کامپیوتر، بینایی کامپیوتر، هوش مصنوعی، یادگیری ماشین، و الگوریتم‌ها و محاسبات است که ارتباط تنگاتنگی میان تمام آنهاست. در نتیجه در این صفحه علاوه بر معرفی این فیلد، نقشه راهی نیز برای علاقه‌مندان این حوزه ارائه کرده‌ایم.: ماتریس های مجاورت نشان‌دهنده رابطه مجاورت بین پیکسل‌ها در یک تصویر هستند.
یافتن کوتاه‌ترین مسیر بین دو گره: با انجام ضرب ماتریس بر روی ماتریس مجاورت، می‌توان کوتاه‌ترین مسیر را بین هر دو گره در یک نمودار دید.

حتما بخوانید :

فیلم‌های آموزشی ریاضی گسسته

جمع‌بندی

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

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

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

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

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