advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود برنامه هشت وزیر با جستجوی عمقی در سی شارپ

دانلود برنامه هشت وزیر با جستجوی عمقی در سی شارپ

3000 تومان
دانلود پروژه وب سایت اشعار با ASP.NET و SQL

دانلود پروژه وب سایت اشعار با ASP.NET و SQL

3000 تومان
دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

4800 تومان
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

14000 تومان
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

3000 تومان

ساختمان داده گراف Graph

گراف، مجموعه ای از نقاط است که بعضی از آن نقاط توسط خطوطی به هم وصل میشوند. هر نقطه را یک رأس یا گره، و هر اتصال را یک یال می نامیم. نقشه راههای استان را میتوان یک گراف در نظر گرفت، بطوریکه نقاط برخورد جاده بعنوان راس و خود جاده ها بعنوان یال محسوب میشوند.
ساختمان داده گراف Graph

ساختمان داده گراف Graph

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

تعریف گراف

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

 

انواع گراف ها

تمام گرافهایی که برای نمایش شبکه ها مورد استفاده قرار میگیرند، یکسان نیستند. گراف بطور کلی به دودسته تقسیم میشوند:

• گرافهای جهتدار

• گرافهای بدون جهت

گراف جهتدار گرافی است که در آن، یالی از راس v به v دارای جهت است و چنین یالی را بصورت نمایش میدهیم که یک زوج مرتب است. اگر ترتیب رئوس عوض شود، همان یال در نظر پرفته نخواهد شد.

گراف بدون جهت گرافی است که در آن یالی بین v و v فاقد جهت است. چنین یالی را بصورت (v, v) نمایش میدهیم که زوج مرتب نیست. یعنی یال (v, v) همان یال (v₂, v) است.

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

 

اصطلاحات مربوط به ساختمان داده گراف

• گره های همجوار : اگر در گراف از گره x به گره y یالی وجود داشته باشد، آن دو گره همجوارند.

• حلقه : اگر یالی وجود داشته باشد که گره های شروع و پایان آن یکسان باشد، حلقه بوجود می آید.

• مولفه : هر گراف میتواند از چند تکه تشکیل شده باشد که هر تکه از آنرا یک مولفه گویند.

• مسیر : دنباله ای از گره هاست که در آن هر گره، همجوار گره دیگری است. طول مسیر برابر با تعداد  یالهای موجود در آن مسیر است.

• چرخه : مسیری با طول بیش از یک است که از یک گره شروع و به همان گره ختم میشود.

• یالهای موازی : اگر بیش از یک یال بین دو گره وجود داشته باشد، آنها را یالهای موازی گویند.

• درجه گره : در گراف بدون جهت، درجه ی گره ای مثل x برابر با تعداد یالهایی است که در آن گره تلاقی میکنند. اگر گراف جهتدار باشد، درجه ورودی گره ای مثل x برابر با تعدا یالهایی است که به آن وارد میشوند و درجه خروجی گرهی مثل x برابر با تعدا  یالهایی است که از آن خارج میشوند.

• گراف متصل : در گراف، دو گره x و y درصورتی متصل هستند که مسیری از یکی از گره ها به دیگری وجود داشته باشد. گراف بدون جهت در صورتی متصل است که به ازای هر گره x و y در آن مسیری وجود داشته باشد. گراف جهتدار در صورتی متصل است که به ازای هر دو گره x و y در آن مسیری از x به y و از y به x وجود داشته باشد.

 

پیاده سازی یا نمایش گراف

گراف را به شکل های مختلفی میتوان نمایش داد که متداولترین آنها به شرح زیر می باشد:

  • پیاده سازی گراف با مجموعه ها
  • پیاده سازی گراف با ماتریس های همجواری
  • پیاده سازی گراف با لیست همجواری
  • پیاده سازی گراف با لیست یال ها

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

عملیات های مختلف مربوط به گراف مثل حذف و اضافه ی گره ها و یالها، پیمایش یا جستوجو در نمایش گراف بصورت ماتریس همجواری چندان آسان نیست ولی این کارها در نمایش های پیوندی گراف به آسانی انجام میشوند. علاوه براین در نمایش گراف با ماتریس همجواری، لازم است همواره یک ماتریس n*n ایجاد شود که n تعداد گره هاست. امتیاز ماتریس همجواری کارایی آن است. 

 

 



1
نظرات
  • user avatar Seyed Ali:
    ۰۷:۴۲:۳۴ __ ۱۳۹۶/۱۰/۰۵

    مختصر و مفید بود.

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
آشنایی با ساختمان داده گراف Graphنمایش گراف و پیاده سازی گرافگراف Graph چیست؟graph Data Structureآشنایی با Graph Data Structure تعریف گراف و انواع گراف هاآشنایی با ساختار گرافهااصطلاحات مربوط به ساختمان داده گرافتبلیغات ارزان سایت آموزش برنامه نویسیتبلیغات مخصوص طراحان وب سایتتبلیغات در سایت برنامه نویسیتبلیغات اینترنتی برای برنامه نویساندر آغوش مینیمالیسممنوی همبرگر با سه خط افقی که روی یکدیگر قرار گرفته اند نشانه چیست؟ سوئیچ به یک ستون واحدتبدیل متن ساده به وبلاگ و سایت های پویا با React.jsکتابخانه sass برای استفاده آسان تر از آنکتابخانه سطح بالا برای اتوماتیک سازی اعمال مرورگر لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

سفارش پروژه در سورس کد

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php