گراف وزندار
(تغییرمسیر از گراف وزن دار)
گراف وزندار (نام علمی: weighted graph)، گرافی است که به هر یال آن عددی نسبت داده شدهاست[۱] که وزن آن یال میباشد. یا به راس آن عددی نسبت داده شده. وزن یال میتواند نشان دهنده هزینه، مسافت، زمان یا هر مشخصه دیگری از یال باشد. بعضی از نویسندهها به آن گراف شبکهای میگویند.[۲] از گراف وزندار برای حل مسائلی چون فروشنده دورهگرد استفاده میشود.درگراف وزندار، وزنها را در ماتریس مجاورت ذخیره میکنند.
انواع گراف وزندار
ویرایش- گرافی که راسهای آن دارای وزن میباشند.
- گرافی که یالهای آن دارای وزن میباشند.
- گرافی که هم راس و هم یالهای آن دارای وزن میباشند.[۳]
وزن یالها
ویرایشوزن هر یال یک گراف موزون میتواند نشان دهنده یکی از موارد زیر باشد:
- هزینه یا مسافت: میزان هزینه یا مقدار مسافت برای جابه جایی از یک راس (مکان) به راس دیگر.
- ظرفیت: حد اکثر میزان چیزی که میتواند از یک راس (مکان) به راس دیگر منتقل شود.
پیادهسازی گراف وزندار
ویرایشکلاس مربوط به پیادهسازی یالها:
public class Edge
{ int NodeID; // The neighbor node double Weight; // وزن یال Node next; // Link variable }
کلاس مربوط به پیادهسازی گراف
public class Graph
{ public Edge[] graph; // Array of Edges }
نمایش گراف با استفاده از ماتریس مجاورت
- اگر بین دو راس i و j هیچ یالی نباشد، مقدار a[i][j] را برابر بینهایت قرار میدهیم.
- اگر بین دو راس i و j یالی باشد، مقدار a[i][j] را برابر ارزش آن یال قرار میدهیم.
کلاس مربوط به پیادهسازی گراف وزندار با استفاده از ماتریس مجاورت
public class Graph
{ double[][] M; // M[i][j] = weight of edge (i,j) ... }
منابع
ویرایش- ↑ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (International student ed.). Boston: PWS-KENT Pub. Co. p. 463. ISBN 0-534-92373-9. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.
- ↑ Strang, Gilbert (2005), Linear Algebra and Its Applications (4th ed.), Brooks Cole, ISBN 0-03-010567-6
- ↑ Weisstein, Eric W. "Weighted Graph." From MathWorld--A
🔥 Top keywords: صفحهٔ اصلیمسعود پزشکیانسعید جلیلیمحمدباقر قالیبافویژه:جستجوانتخابات ریاستجمهوری ایران (۱۴۰۳)عبدالرسول زرینمصطفی پورمحمدیسید امیرحسین قاضیزاده هاشمیرده:پوزیشنهای جنسیعلیرضا زاکانیجام ملتهای اروپا ۲۰۲۴در انتهای شب (مجموعه نمایش خانگی ۱۴۰۳)مریم رجویروشهای آمیزش جنسیرده:فیلمهای سکسی-کمدی آمریکاییآمیزش جنسی بدون دخولانتخابات ریاستجمهوری ایران (۱۴۰۰)سید ابراهیم رئیسیجام ملتهای اروپانامزدهای انتخابات ریاستجمهوری ایران (۱۴۰۳)سید علی خامنهایلحظه گرگ و میشسکس شاپسید محمد خاتمینوری شاهینفهرست نخستوزیران ایرانزخم کاریجام ملتهای اروپا ۲۰۲۰حسین عبده تبریزیآمیزش جنسی دهانیافعی تهرانفرجلیسیایرانهدی زینالعابدینهمستر کامبتمحمود احمدینژادآمیزش جنسیآیدا پناهنده