مسیر رتبه‌برترشدن در کنکور ارشد مهندسی کامپیوتر و IT
ثبت‌نام رایگان
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

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

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

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

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

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

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

لیست مجاورت

در این روش آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100آموزش آرایه در ساختمان داده به زبان ساده و از 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;
};

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

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

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

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

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

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

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

مزایا

معایب

کاربردها

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

جمع‌بندی

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

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

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

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

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

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