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

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

انواع نمایش گراف

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

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

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

لیست مجاورت

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

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

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

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

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

در اینجا 0، 1، 2 و 3 رئوس هستند و هر کدام یک لیست پیوندی با تمام رئوس مجاور خود تشکیل می‌دهند. برای مثال، راس 1 دارای دو رأس مجاور 0 و 2 است، بنابراین در شکل بالا، 1 به 0 و 2 لینک شده است.

ساده‌ترین فهرست مجاورت، به یک ساختار داده گره، برای ذخیره یک راس و یک ساختار داده گراف برای سازماندهی گره‌ها نیاز دارد. ما به تعریف اصلی یک گراف رجوع می‌کنیم یعنی مجموعه‌ای از رئوس و یال ها {V, E}. برای سادگی، از یک گراف بدون برچسب به جای یک گراف برچسب‌دار استفاده می‌کنیم، یعنی راس‌ها با شاخص‌های 0،1،2،3 خود مشخص می‌شوند.

بیایید ساختارهای داده‌ای که در بالا ذکر کردیم را بررسی کنیم:

struct node{
    int vertex;
    struct node* next;
};

struct Graph{
    int numVertices;
    struct node** adjLists;
};

struct node{
    int vertex;
    struct node* next;
};

struct Graph{
    int numVertices;
    struct node** adjLists;
};

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

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

Python

class AdjNode:
    def __init__(self, value):
        self.vertex = value
        self.next = None

class Graph:
    def __init__(self, num):
        self.V = num
        self.graph = [None] * self.V

    # Add edges
    def add_edge(self, s, d):
        node = AdjNode(d)
        node.next = self.graph[s]
        self.graph[s] = node

        node = AdjNode(s)
        node.next = self.graph[d]
        self.graph[d] = node

    # Print the graph
    def print_agraph(self):
        for i in range(self.V):
            print("Vertex " + str(i) + ":", end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")
if __name__ == "__main__":
    V = 5

    # Create graph and edges
    graph = Graph(V)
    graph.add_edge(0, 1)
    graph.add_edge(0, 2)
    graph.add_edge(0, 3)
    graph.add_edge(1, 2)

    graph.print_agraph()

class AdjNode:
    def __init__(self, value):
        self.vertex = value
        self.next = None

class Graph:
    def __init__(self, num):
        self.V = num
        self.graph = [None] * self.V

    # Add edges
    def add_edge(self, s, d):
        node = AdjNode(d)
        node.next = self.graph[s]
        self.graph[s] = node

        node = AdjNode(s)
        node.next = self.graph[d]
        self.graph[d] = node

    # Print the graph
    def print_agraph(self):
        for i in range(self.V):
            print("Vertex " + str(i) + ":", end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")
if __name__ == "__main__":
    V = 5

    # Create graph and edges
    graph = Graph(V)
    graph.add_edge(0, 1)
    graph.add_edge(0, 2)
    graph.add_edge(0, 3)
    graph.add_edge(1, 2)

    graph.print_agraph()

Java

import java.util.*;

class Graph {

  // Add edge
  static void addEdge(ArrayListArrayList> am, int s, int d) {
    am.get(s).add(d);
    am.get(d).add(s);
  }

  public static void main(String[] args) {

    // Create the graph
    int V = 5;
    ArrayListArrayList> am = new ArrayListArrayList>(V);

    for (int i = 0; i  V; i++)
      am.add(new ArrayList());

    // Add edges
    addEdge(am, 0, 1);
    addEdge(am, 0, 2);
    addEdge(am, 0, 3);
    addEdge(am, 1, 2);

    printGraph(am);
  }

  // Print the graph
  static void printGraph(ArrayList<ArrayList> am) {
    for (int i = 0; i  am.size(); i++) {
      System.out.println("\nVertex " + i + ":");
      for (int j = 0; j  " + am.get(i).get(j));
      }
      System.out.println();
    }
  }
}

import java.util.*;

class Graph {

  // Add edge
  static void addEdge(ArrayListArrayList> am, int s, int d) {
    am.get(s).add(d);
    am.get(d).add(s);
  }

  public static void main(String[] args) {

    // Create the graph
    int V = 5;
    ArrayListArrayList> am = new ArrayListArrayList>(V);

    for (int i = 0; i  V; i++)
      am.add(new ArrayList());

    // Add edges
    addEdge(am, 0, 1);
    addEdge(am, 0, 2);
    addEdge(am, 0, 3);
    addEdge(am, 1, 2);

    printGraph(am);
  }

  // Print the graph
  static void printGraph(ArrayList<ArrayList> am) {
    for (int i = 0; i  am.size(); i++) {
      System.out.println("\nVertex " + i + ":");
      for (int j = 0; j  " + am.get(i).get(j));
      }
      System.out.println();
    }
  }
}

C

#include 
#include 

struct node
{
    int vertex;
    struct node *next;
};
struct node *createNode(int);

struct Graph
{
    int numVertices;
    struct node **adjLists;
};

// Create a node
struct node *createNode(int v)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
struct Graph *createAGraph(int vertices)
{
    struct Graph *graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct node *));

    int i;
    for (i = 0; i adjLists[i] = NULL;

    return graph;
}

// Add edge
void addEdge(struct Graph *graph, int s, int d)
{
    // Add edge from s to d
    struct node *newNode = createNode(d);
    newNode->next = graph->adjLists[s];
    graph->adjLists[s] = newNode;

    // Add edge from d to s
    newNode = createNode(s);
    newNode->next = graph->adjLists[d];
    graph->adjLists[d] = newNode;
}

// Print the graph
void printGraph(struct Graph *graph)
{
    int v;
    for (v = 0; v numVertices; v++)
    {
        struct node *temp = graph->adjLists[v];
        printf("\n Vertex %d\n: ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main()
{
    struct Graph *graph = createAGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);

    printGraph(graph);

    return 0;
}

#include 
#include 

struct node
{
    int vertex;
    struct node *next;
};
struct node *createNode(int);

struct Graph
{
    int numVertices;
    struct node **adjLists;
};

// Create a node
struct node *createNode(int v)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
struct Graph *createAGraph(int vertices)
{
    struct Graph *graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct node *));

    int i;
    for (i = 0; i adjLists[i] = NULL;

    return graph;
}

// Add edge
void addEdge(struct Graph *graph, int s, int d)
{
    // Add edge from s to d
    struct node *newNode = createNode(d);
    newNode->next = graph->adjLists[s];
    graph->adjLists[s] = newNode;

    // Add edge from d to s
    newNode = createNode(s);
    newNode->next = graph->adjLists[d];
    graph->adjLists[d] = newNode;
}

// Print the graph
void printGraph(struct Graph *graph)
{
    int v;
    for (v = 0; v numVertices; v++)
    {
        struct node *temp = graph->adjLists[v];
        printf("\n Vertex %d\n: ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main()
{
    struct Graph *graph = createAGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 0, 3);
    addEdge(graph, 1, 2);

    printGraph(graph);

    return 0;
}

C++

#include <bits/stdc++.h>
using namespace std;

// Add edge
void addEdge(vector adj[], int s, int d)
{
    adj[s].push_back(d);
    adj[d].push_back(s);
}

// Print the graph
void printGraph(vector adj[], int V)
{
    for (int d = 0; d  V; ++d)
    {
        cout  "\n Vertex "
              d  ":";
        for (auto x : adj[d])
            cout  "  x;
        printf("\n");
    }
}

int main()
{
    int V = 5;

    // Create a graph
    vector adj[V];

    // Add edges
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 0, 3);
    addEdge(adj, 1, 2);
    printGraph(adj, V);
}

#include <bits/stdc++.h>
using namespace std;

// Add edge
void addEdge(vector adj[], int s, int d)
{
    adj[s].push_back(d);
    adj[d].push_back(s);
}

// Print the graph
void printGraph(vector adj[], int V)
{
    for (int d = 0; d  V; ++d)
    {
        cout  "\n Vertex "
              d  ":";
        for (auto x : adj[d])
            cout  "  x;
        printf("\n");
    }
}

int main()
{
    int V = 5;

    // Create a graph
    vector adj[V];

    // Add edges
    addEdge(adj, 0, 1);
    addEdge(adj, 0, 2);
    addEdge(adj, 0, 3);
    addEdge(adj, 1, 2);
    printGraph(adj, V);
}

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

لیست پیوندی چیست؟ آموزش لیست پیوندی ساده، دو طرفه و حلقوی

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

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

مزایا

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

معایب

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

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

خرید فیلم ساختمان داده

کاربردها

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

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

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

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

جمع‌بندی

در نظریه گرافهمه چیز در مورد نظریه گراف (Graph Theory)در این مقاله یک مقدمه جامع در رابطه با نظریه گراف ارائه شده است و سعی شده نشان داده شود که دانستن برخی از مبانی نظریه گراف تا چه میزان می‌تواند مفید و موثر باشد. و علوم کامپیوترعلوم کامپیوتر یا کامپیوتر ساینس چیستدر این صفحه به بررسی و موشکافی رشته علوم کامپیوتر اعم از بررسی بازار کار، گرایش‌ها، دروس و چارت درسی این رشته، میزان درآمد و حقوق فارغ التحصیلان این رشته و ادامه تحصیل در این رشته پرداخته‌ شده است.، لیست مجاورت مجموعه‌ای از لیست‌های نامرتب است که یک گراف متناهی را نشان می‌دهد. در این مقاله به بررسی این ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است ها پرداختیم ؛ همینطور با پیاده‌سازی، مزایا و معایب و کاربردهای لیست مجاورت آشنا شدیم.

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

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

چرا لیست مجاورت بهتر از ماتریس مجاورت است؟

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