ساخت الگوریتم های گراف در سوئیفت — به زبان ساده

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

مبانی گراف

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

فیلم آموزش گراف در ساختمان گسسته (رایگان) در فرادرس

کلیک کنید

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

جهت‌دار یا غیر جهت‌دار

چنان که در بخش قبل دیدیم، روش‌های زیادی برای پیکربندی یک گراف وجود دارد. یک گزینه اضافی برای تنظیم مدل به صورت جهت‌دار یا غیر جهت‌دار نیز وجود دارد. نمونه‌های فوق همگی گراف‌های غیر جهت‌دار را نشان می‌دادند. به بیان دیگر اتصال بین رأس‌های A و B معادل اتصال بین رأس‌های B و A است. شبکه‌های اجتماعی نمونه‌ای عالی از گراف‌های غیر جهت‌دار هستند. زمانی که درخواستی پذیرفته می‌شود، هر دو طرف (فرستنده و گیرنده) اتصال دوطرفه‌ای با هم پیدا می‌کنند.

سرویسی مانند Google Maps نمونه‌ای عالی از یک گراف جهت‌دار است. برخلاف یک گراف غیر جهت‌دار، گراف‌های جهت‌دار تنها از اتصال یک طرفه بین رأس‌ها و مقاصدشان پشتیبانی می‌کنند. بنابراین برای مثال رأس A می‌تواند به رأس B وصل شود، اما A لزوماً از طریق B قابل دسترسی نیست. برای نمایش تنوع روابط بین رأس‌ها، گراف‌های جهت‌دار با استفاده از خط‌ها و فلش‌ها ترسیم می‌شوند.

یال و وزن

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

رأس

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

1public class Vertex {
2    
3    var key: String?
4    var neighbors: Array<Edge>
5init() {
6        self.neighbors = Array<Edge>()
7    }
8        
9}

همچنان که در ساختارهای دیگر دیدیم، کلید نماینده داده‌هایی است که با یک وهله از کلاس مرتبط هستند. برای این که همه چیز سرراست باشد، کلید ما به صورت یک رشته اعلان می‌شود. در اپلیکیشن‌های عملی، نوع کلید می‌تواند با یک placeholder ژنریک مانند <T> جایگزین شود. بدین ترتیب می‌توانیم از کلید برای ذخیره‌سازی هر چیزی مانند یک عدد صحیح، حساب یا پروفایل استفاده کنیم.

فهرست همسایگی (ADJACENCY LISTS)

مشخصه همسایگی، آرایه‌ای است که اتصال‌های ممکن از یک رأس به دیگر رئوس را نشان می‌دهد. چنان که قبلاً توضیح دادیم یک رأس می‌تواند با یک یا چند رأس دیگر مرتبط باشد. آیتم‌های فهرست همسایگی گاهی اوقات به نام ADJACENCY LISTS نیز نامیده می‌شوند و می‌توانند برای حل برخی از مسائل مورد استفاده قرار گیرند. در ادامه یک ساختمان داده ابتدایی را می‌بیند که یک یال را نمایش می‌دهد:

1public class Edge {
2    
3    var neighbor: Vertex
4    var weight: Int
5    
6    init() {
7        weight = 0
8        self.neighbor = Vertex()
9    }
10    
11}

ساخت گراف

اکنون که اشیای رأس و یال ساخته شده‌اند، می‌توانیم از این ساختمان‌ها برای ساخت گراف استفاده کنیم. برای این که همه چیز سرراست بماند، فعلاً روی عملیات اساسی افزودن و پیکربندی رئوس متمرکز می‌شویم:

1public class Edge {
2    
3    var neighbor: Vertex
4    var weight: Int
5    
6    init() {
7        weight = 0
8        self.neighbor = Vertex()
9    }
10    
11}

تابع addVertex یک رشته می‌پذیرد که برای ایجاد یک رأس جدید مورد استفاده قرار می‌گیرد. کلاس SwiftGraph یک مشخصه خصوصی به نام canvas نیز دارد که برای مدیریت همه رئوس استفاده می‌شود. از canvas برای ردگیری و مدیریت رأس‌ها با یا بدون یال‌ها می‌تواند استفاده شود، گرچه الزامی نیست.

ایجاد اتصال‌ها

زمانی که رأسی اضافه شد، می‌تواند به رئوس دیگر وصل شود. فرایند تثبیت یک یال به صورت زیر است:

1public class SwiftGraph {
2       
3    //declare graph canvas
4    private var canvas: Array<Vertex>
5    public var isDirected: Bool    
6    
7    init() {
8        canvas = Array<Vertex>()
9        isDirected = true
10    }
11        
12    //create a new vertex
13    func addVertex(key: String) -> Vertex {        
14        
15        //set the key
16        let childVertex: Vertex = Vertex()
17        childVertex.key = key
18        
19        
20        //add the vertex to the graph canvas
21        canvas.append(childVertex)        
22        
23        return childVertex
24    }
25}

تابع addEdge دو رأس دریافت می‌کند که به نام مبدأ و همسایه شناخته می‌شوند. از آنجا که مدل ما به صورت پیش‌فرض یک گراف جهت‌دار است، یک یال جدید ایجاد می‌شود و به فهرست همسایگی رأس مبدأ تنظیم می‌شود. برای یک گراف غیر جهت‌دار یک یال اضافی ایجاد شده و به رأس همسایگی اضافه می‌شود.

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

• مجموعه آموزش‌های برنامه‌‌نویسی
• آموزش برنامه نویسی Swift (سوئیفت) برای برنامه نویسی iOS
• مجموعه آموزش‌های دروس علوم و مهندسی کامپیوتر
• فریمورک Combine در سوئیفت — راهنمای شروع به کار
• آموزش سوئیفت (Swift) — مجموعه مقالات مجله فرادرس

==