۱۳۹۹/۰۵/۱۸

آموزش نحوه نمایش گراف

نمایش گراف در ساختمان داده ها ۱۳۹۸/۰۴/۲۶

نحوه نمایش گراف در ساختمان داده ها

روش اول

ماتریس مجاورتی یا هم جواری در ساختمان داده ها

ماتریس مجاورتی یا هم جواری:G=(V.E) یک گراف با n راس می باشد.آنگاه ماتریس های همجواری آن ماتریس است N*N که هر سطر یا ستون آن node ها یا گره ها مشخص می کند

اگر راس i با راس j مجاور باشد.آنگاه در ماتریس مجاورتی آن خانه برابر 1 میباشد.

اما اگر i , j همجوار نباشند.این خانه از ماتریس دارای مقدار صفر میباشد.

 

نمایش گراف-ساختمان داده ها-ساختمان داده-graph-علوم کامپیوترنحوه نمایش گراف

ماتریس مجاورت غیر جهت دار یک ماتریس غیرمتقارن است.زیرا اگر از i به j وصل باشیم .از j به i هم وصل میباشیم.ماتریس مجاورت فقط از صفر و یک تشکیل شده است.

در گراف ساده ماتریس مجاورت آن دارای قطر اصلی صفر است.

ماتریس مجاورتی یک ماتریس متقارن نسبت به قطر اصلی است.جمع درایه های هر سطر یا ستون برابر درجه نظیر آن سطر یا ستون است.جمع تمام درایه های یک ماتریس برابر جمع درجات آن گراف و برابر تعداد یال ها است.

خوبی روش ماتریس مجاورتی آن است که اکثر الگوریتم ها را میتوان به ساذگی پیاده سازی کرد.

اما مشکلات آن این است که اگر راسی اضافه  و یا کم شود.تغییر ماتریس مجاورتی سخت است.

ماتریس برخورد در ساختمان داده

در این ماتریس تعداد ردیف ها با تعداد گره ها و تعداد ستون ها برابر است با تعداد لبه ها.یعنی در گراف با n راس و e یال تعداد لبه ها .یعنی در گرافی با n راس و e یال ماتریسی n ردیفی و e ستونی داریم.

نمایش گراف-ساختمان داده ها-ساختمان داده-graph-علوم کامپیوترنمایش گراف-ساختمان داده ها-ساختمان داده-graph-علوم کامپیوتر

در این ماتریس واضح است که جمع درایه های هر ردیف برابر است با درجه آن ردیف و آن راس و جمع درایه هر ستون برابر است با 2L

روش سوم :

لیست مجاورتی یا هم جواری در ساختمان داده ها

در این روش آرایه ای داریم که تعداد خانه های آن برابر است با تعداد گره ها با راس ها یا node ها و هر خانه آرایه اشاره می کند به لیستی که این لیست node های مجاور آن راس را نمایش میدهد.یکی از فواید این روش این است که تغییرات روی node ها مثل اضافه و کم کردن node ها با قطع وصل کردن یال ها براحتی انجام میشود.و از معایب آن این است که فضای زیادی برای ذخیره این لیست نیاز است. 

نمایش گراف-ساختمان داده ها-ساختمان داده-graph-علوم کامپیوتر  


رای :

نمایش گراف

ساختمان داده ها

ساختمان داده

graph

علوم کامپیوتر

ارسال نظر
Copyright © All right reserved.