ادامه کد بالا☝️☝️

# بررسی جلوی صف پس از عملیات
print("Front element after dequeue:", c_queue.front_element())  # خروجی: 30

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

(⚠️ابنجا کیلیک کن تا بیشتر یاد بگیری⚠️)

#صف #پشته #پایتون #ساختمان_داده #آموزش

پارت ۵: صف‌های اولویت‌دار و پیاده‌سازی آن‌ها 🎯🚦

سلام دوستان! 🌟 در این پارت از سری آموزشی، به بررسی صف‌های اولویت‌دار (Priority Queue) و نحوه پیاده‌سازی آن‌ها می‌پردازیم. صف‌های اولویت‌دار یکی از مفاهیم مهم در الگوریتم‌ها و برنامه‌نویسی هستند که در مدیریت داده‌های حساس به اولویت بسیار کاربرد دارند. بیایید شروع کنیم! 🚀

صف اولویت‌دار (Priority Queue) چیست؟ 🤔

صف اولویت‌دار (Priority Queue) نوع خاصی از صف است که در آن هر عنصر دارای یک اولویت است. برخلاف صف معمولی که عناصر بر اساس ترتیب ورود به صف از آن خارج می‌شوند، در صف‌های اولویت‌دار، عناصری که اولویت بالاتری دارند، زودتر از دیگران از صف خارج می‌شوند.

برای مثال، در یک سیستم اورژانس پزشکی، بیماران بر اساس شدت بیماری‌شان درمان می‌شوند، نه بر اساس زمان ورودشان به بیمارستان. بیمار با شرایط بحرانی‌تر اولویت بالاتری دارد و زودتر درمان می‌شود.

ویژگی‌های صف اولویت‌دار 📌

- اولویت: هر عنصر در صف اولویت‌دار دارای یک مقدار اولویت است. هر چه مقدار اولویت کمتر باشد، اولویت آن عنصر بیشتر است.
- ترتیب خروج: عنصری که دارای بالاترین اولویت (کمترین مقدار اولویت) است، زودتر از صف خارج می‌شود.

کاربردهای صف‌های اولویت‌دار 💻

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

1. الگوریتم‌های مسیریابی: در الگوریتم‌هایی مانند دیکسترا، صف‌های اولویت‌دار برای پیدا کردن کوتاه‌ترین مسیر استفاده می‌شوند.
2. زمان‌بندی پردازنده: سیستم‌های عامل از صف‌های اولویت‌دار برای مدیریت فرآیندها استفاده می‌کنند تا فرآیندهای با اولویت بالاتر زودتر اجرا شوند.
3. مدیریت وظایف: در سیستم‌های مدیریت پروژه و صف‌های وظایف، از صف‌های اولویت‌دار برای ترتیب‌دهی و مدیریت وظایف بر اساس اهمیت استفاده می‌شود.

پیاده‌سازی صف اولویت‌دار 🛠️

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

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item, priority):
        self.queue.append((item, priority))
        self.queue.sort(key=lambda x: x[1])

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)[0]
        else:
            return "Queue is empty"

    def front(self):
        if not self.is_empty():
            return self.queue[0][0]
        else:
            return "Queue is empty"

    def is_empty(self):
        return len(self.queue) == 0

مثال کاربردی 📚

بیایید ببینیم چطور می‌توانیم از این صف اولویت‌دار استفاده کنیم:

# ایجاد یک صف اولویت‌دار
pq = PriorityQueue()

# اضافه کردن عناصر با اولویت‌های مختلف
pq.enqueue('Task 1', 2)
pq.enqueue('Task 2', 1)
pq.enqueue('Task 3', 3)

# مشاهده عنصر جلوی صف (با بالاترین اولویت)
print("Front element:", pq.front())  # خروجی: Task 2

# حذف عنصر با بالاترین اولویت
print("Dequeued element:", pq.dequeue())  # خروجی: Task 2

# مشاهده عنصر جلوی صف پس از حذف
print("Front element after dequeue:", pq.front())  # خروجی: Task 1

پیچیدگی زمانی صف اولویت‌دار ⏱️

در پیاده‌سازی صف اولویت‌دار با لیست، هر بار که عنصری به صف اضافه می‌شود، صف باید مرتب شود. بنابراین:

- **پیچیدگی زمانی enqueue:** در بدترین حالت O(n log n) است (با توجه به مرتب‌سازی).
- **پیچیدگی زمانی dequeue:** به دلیل اینکه عنصر اول را برمی‌داریم، این عملیات در O(1) انجام می‌شود.

برای بهبود پیچیدگی زمانی، می‌هیپ‌ها (Heaps) برای پیاده‌سازی صف‌های اولویت‌دار استفاده کرد که در آن زمان درج و حذف هر دو O(log n) است.


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

👈اینم لینک کانال منه 👉

#صف_اولویت‌دار #پایتون #ساختمان_داده #آموزش

پارت ۶: پروژه عملی: مدیریت سفارشات یک فروشگاه آنلاین 🛒💻

سلام دوستان! 🌟 در این پارت آخر از سری آموزشی، یک پروژه عملی را پیاده‌سازی می‌کنیم که شامل مفاهیم پشته و صف می‌شود. هدف این پروژه، مدیریت سفارشات یک فروشگاه آنلاین است که نیازمند بهینه‌سازی و اولویت‌بندی درخواست‌هاست. این پروژه یک مثال کاربردی از چگونگی استفاده از ساختمان داده‌های پشته و صف در دنیای واقعی است. بیایید شروع کنیم! 🚀

تعریف مسئله 📋

فرض کنید شما در حال توسعه یک سیستم مدیریت سفارشات برای یک فروشگاه آنلاین هستید. این سیستم باید بتواند:
1. ثبت سفارشات جدید را انجام دهد و آن‌ها را بر اساس اولویت در یک صف قرار دهد.
2. نمایش آخرین سفارش ثبت شده (با استفاده از پشته) برای بررسی سریع.
3. مدیریت صف انتظار سفارشات (پردازش صف).

جزئیات پیاده‌سازی 🛠️

ما نیاز به دو ساختمان داده داریم:
- صف اولویت‌دار (Priority Queue): برای مدیریت سفارشات بر اساس اولویت.
- پشته (Stack): برای ذخیره آخرین سفارش ثبت شده جهت دسترسی سریع.

کدنویسی پروژه 💻

ابتدا باید کلاس‌های مربوط به صف و پشته را ایجاد کنیم.

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            return "Stack is empty"

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return "Stack is empty"

    def is_empty(self):
        return len(self.stack) == 0

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item, priority):
        self.queue.append((item, priority))
        self.queue.sort(key=lambda x: x[1])

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)[0]
        else:
            return "Queue is empty"

    def front(self):
        if not self.is_empty():
            return self.queue[0][0]
        else:
            return "Queue is empty"

    def is_empty(self):
        return len(self.queue) == 0

مدیریت سفارشات 🛒

اکنون باید کلاس مدیریت سفارشات را پیاده‌سازی کنیم که از پشته و صف اولویت‌دار استفاده می‌کند.

class OrderManager:
    def __init__(self):
        self.orders = PriorityQueue()
        self.recent_orders = Stack()

    def add_order(self, order_id, priority):
        self.orders.enqueue(order_id, priority)
        self.recent_orders.push(order_id)
        print(f"Order {order_id} added with priority {priority}")

    def process_order(self):
        if not self.orders.is_empty():
            order_id = self.orders.dequeue()
            print(f"Processing order {order_id}")
        else:
            print("No orders to process")

    def show_recent_order(self):
        recent_order = self.recent_orders.peek()
        print(f"Most recent order: {recent_order}")

# مثال استفاده از OrderManager
manager = OrderManager()

# اضافه کردن سفارشات
manager.add_order('Order_001', 3)
manager.add_order('Order_002', 1)
manager.add_order('Order_003', 2)

# نمایش آخرین سفارش ثبت شده
manager.show_recent_order()  # خروجی: Order_003

# پردازش سفارشات
manager.process_order()  # خروجی: Order_002
manager.process_order()  # خروجی: Order_003
manager.process_order()  # خروجی: Order_001

شرح پروژه 📑

1. اضافه کردن سفارشات:
- هر سفارش شامل یک شناسه (ID) و یک اولویت است.
- سفارشات به صف اولویت‌دار اضافه می‌شوند و بر اساس اولویت مرتب می‌گردند.
- همچنین سفارشات در پشته ذخیره می‌شوند تا بتوان آخرین سفارش ثبت شده را مشاهده کرد.

2. پردازش سفارشات:
- سفارشات بر اساس اولویت از صف خارج می‌شوند.
- سفارش با اولویت بالاتر (مقدار کمتر) زودتر پردازش می‌شود.

3. نمایش آخرین سفارش:
- با استفاده از پشته، می‌توان آخرین سفارش ثبت شده را به راحتی مشاهده کرد.


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

این بود پایان سری سوم از آموزش ساختمان داده‌ها! امیدوارم این پروژه و مفاهیم تدریس شده در این سری برای شما مفید بوده باشند. اگر سوال یا نظری دارید، خوشحال می‌شوم که به آن‌ها پاسخ دهم! 🌟

اینم لینک کانال منه روش کلیک کن تا بیشتر یاد بگیری

#پروژه_عملی #پایتون #ساختمان_داده #آموزش

☝️☝️سری سوم آموزش ساختمان داده: پشته (Stack) و صف (Queue)☝️☝️

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۱: معرفی درخت‌ها

درخت چیست؟ 🌳

درخت یک ساختار داده‌ای غیرخطی است که از مجموعه‌ای از گره‌ها (Nodes) تشکیل شده. هر گره شامل یک مقدار (Value) و ارجاع به گره‌های فرزند خود است. گره‌ای که بالاترین سطح را دارد و هیچ گره‌ای به آن اشاره نمی‌کند، به عنوان ریشه (Root) شناخته می‌شود. سایر گره‌ها می‌توانند فرزند (Child) یا والد (Parent) داشته باشند.

ویژگی‌های اصلی درخت‌ها:
- گره (Node): هر گره شامل یک مقدار و ارجاع به گره‌های فرزند است.
- ریشه (Root): گره‌ای که در بالاترین سطح قرار دارد و نقطه شروع درخت است.
- برگ (Leaf): گره‌هایی که هیچ فرزندی ندارند.
- لبه (Edge): ارتباط بین دو گره (از والد به فرزند).
- سطح (Level): عمق یک گره، یعنی تعداد لبه‌ها از ریشه تا آن گره.
- ارتفاع (Height): بیشترین سطح درخت، یعنی بیشترین تعداد لبه‌ها از ریشه تا برگ.

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

درخت‌ها در بسیاری از مسائل و الگوریتم‌ها کاربرد دارن، از جمله:

1. سیستم فایل‌ها: سیستم‌های فایل (مثل NTFS یا FAT) به شکل درختی سازماندهی می‌شن. دایرکتوری‌ها به عنوان گره‌های والد و فایل‌ها به عنوان گره‌های فرزند یا برگ نمایش داده می‌شن.

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

3. پایگاه داده‌ها: برخی از انواع پایگاه داده‌ها، به ویژه پایگاه‌های داده سلسله مراتبی، از ساختار درخت استفاده می‌کنن.

4. جستجو و مرتب‌سازی: درخت‌های جستجوی دودویی (Binary Search Trees) یکی از مهم‌ترین ساختارهای داده‌ای برای جستجو و مرتب‌سازی کارآمد هستن.

مثال ساده از یک درخت 📝

فرض کنید ما یک سیستم مدیریت پروژه داریم که شامل یک مدیر کل و چند تیم است. هر تیم نیز شامل چند زیرمجموعه و اعضای مختلف است. این ساختار می‌تونه به شکل یک درخت نمایش داده بشه:

مدیر کل (ریشه)
   ├── تیم ۱
   │   ├── عضو ۱
   │   └── عضو ۲
   ├── تیم ۲
   │   ├── عضو ۳
   │   └── عضو ۴
   └── تیم ۳
       ├── عضو ۵
       └── عضو ۶

در این مثال، "مدیر کل" ریشه درخت است و هر تیم به عنوان یک گره فرزند یا والد عمل می‌کنه. اعضا هم گره‌های برگ هستن که هیچ فرزندی ندارن.

در این پارت، با مفاهیم پایه‌ای درخت‌ها آشنا شدیم و فهمیدیم که چرا این ساختار داده‌ای اینقدر مهم و پرکاربرده. در پارت‌های بعدی به بررسی انواع مختلف درخت‌ها و پیاده‌سازی آن‌ها خواهیم پرداخت. آماده‌اید؟ پس همراه باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۲: درخت‌های دودویی (Binary Trees)

توی پارت قبلی، با مفاهیم پایه‌ای درخت‌ها آشنا شدیم. حالا وقتشه که وارد جزئیات بشیم و یکی از مهم‌ترین انواع درخت‌ها رو بررسی کنیم: درخت‌های دودویی (Binary Trees). این نوع درخت یکی از پرکاربردترین‌هاست و پایه خیلی از مباحث پیشرفته‌تر رو تشکیل می‌ده. بیایید شروع کنیم! 🚀



درخت دودویی چیست؟ 🌳

درخت دودویی یک نوع درخت است که هر گره در آن حداکثر دو فرزند دارد. این دو فرزند معمولاً به عنوان فرزند چپ (Left Child) و فرزند راست (Right Child) شناخته می‌شن.

ویژگی‌های اصلی درخت‌های دودویی:
- گره (Node): هر گره شامل یک مقدار و ارجاع به حداکثر دو گره فرزند است.
- فرزند چپ (Left Child): گره‌ای که در سمت چپ گره والد قرار دارد.
- فرزند راست (Right Child): گره‌ای که در سمت راست گره والد قرار دارد.

انواع درخت‌های دودویی 🌲

درخت‌های دودویی خودشون به انواع مختلفی تقسیم می‌شن:

1. درخت دودویی کامل (Complete Binary Tree):
در این نوع درخت، همه سطوح به جز آخرین سطح، به طور کامل پر شده‌اند و در آخرین سطح نیز همه گره‌ها تا حد امکان در سمت چپ قرار گرفته‌اند.

2. درخت دودویی پر شده (Full Binary Tree):
در این نوع درخت، هر گره یا دقیقاً دو فرزند دارد یا هیچ فرزندی ندارد.

3. درخت دودویی متوازن (Balanced Binary Tree):
در این نوع درخت، تفاوت ارتفاع دو زیر درخت فرزند چپ و راست هیچ‌گاه بیشتر از یک نیست. این نوع درخت به کارآمد بودن عملیات‌های مختلف کمک می‌کنه.

پیاده‌سازی یک درخت دودویی ساده 📝

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

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_value):
        self.root = Node(root_value)

    def insert_left(self, current_node, value):
        if current_node.left is None:
            current_node.left = Node(value)
        else:
            new_node = Node(value)
            new_node.left = current_node.left
            current_node.left = new_node

    def insert_right(self, current_node, value):
        if current_node.right is None:
            current_node.right = Node(value)
        else:
            new_node = Node(value)
            new_node.right = current_node.right
            current_node.right = new_node

مثال از درخت دودویی 🌲

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

      1
     / \
    2   3
   / \
  4   5

می‌تونیم این درخت رو با استفاده از کد زیر پیاده‌سازی کنیم:

# ساخت درخت
bt = BinaryTree(1)

# افزودن گره‌ها
bt.insert_left(bt.root, 2)
bt.insert_right(bt.root, 3)
bt.insert_left(bt.root.left, 4)
bt.insert_right(bt.root.left, 5)

عملیات پایه روی درخت دودویی 🛠️

درخت‌های دودویی شامل عملیات‌های پایه‌ای مثل درج (Insert)، حذف (Delete)، و جستجو (Search) هستن. در این پارت فقط با عملیات درج آشنا شدیم. در پارت‌های بعدی به صورت مفصل‌تر به این عملیات‌ها و روش‌های پیمایش درخت خواهیم پرداخت.

در این پارت، با درخت‌های دودویی و ویژگی‌هاشون آشنا شدیم و یک پیاده‌سازی ساده از اون‌ها رو دیدیم. در پارت بعدی به بررسی روش‌های مختلف پیمایش درخت‌های دودویی می‌پردازیم. همراه ما باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #درخت_دودویی #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۳: پیمایش درخت‌ها 🚶‍♂️🌲

در پارت قبلی، با درخت‌های دودویی و پیاده‌سازی اون‌ها آشنا شدیم. حالا وقتشه که به یکی از مهم‌ترین مباحث مرتبط با درخت‌ها بپردازیم: پیمایش درخت‌ها (Tree Traversal). این مبحث به شما کمک می‌کنه تا بتونید تمام گره‌های یک درخت رو به ترتیب‌های مختلف پیمایش کنید و داده‌ها رو به دست بیارید. پس بزن بریم! 🚀


پیمایش درخت‌ها چیست؟ 🌳

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

در این پارت، چهار روش اصلی پیمایش درخت‌ها رو بررسی می‌کنیم:

1. پیمایش پیش‌نورد (Preorder Traversal)
2. پیمایش میانوند (Inorder Traversal)
3. پیمایش پس‌نورد (Postorder Traversal)
4. پیمایش سطح به سطح (Level-order Traversal)

1. پیمایش پیش‌نورد (Preorder Traversal) 🥇

در این روش، ابتدا گره ریشه (Root) بازدید می‌شه، سپس به ترتیب زیر درخت چپ و بعد زیر درخت راست بازدید می‌شن.

ترتیب بازدید:
1. گره ریشه
2. زیر درخت چپ
3. زیر درخت راست

مثال:

فرض کنید درخت زیر رو داریم:

      1
     / \
    2   3
   / \
  4   5

پیمایش پیش‌نورد این درخت به این صورت خواهد بود: 1, 2, 4, 5, 3

پیاده‌سازی:

def preorder_traversal(node):
    if node:
        print(node.value, end=' ')
        preorder_traversal(node.left)
        preorder_traversal(node.right)

2. پیمایش میانوند (Inorder Traversal) 📄

در این روش، ابتدا زیر درخت چپ بازدید می‌شه، سپس گره ریشه و در نهایت زیر درخت راست.

ترتیب بازدید:
1. زیر درخت چپ
2. گره ریشه
3. زیر درخت راست

مثال:

پیمایش میانوند درخت بالا به این صورت خواهد بود: 4, 2, 5, 1, 3

پیاده‌سازی:

def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value, end=' ')
        inorder_traversal(node.right)

3. پیمایش پس‌نورد (Postorder Traversal) 🕒

در این روش، ابتدا زیر درخت چپ، سپس زیر درخت راست و در نهایت گره ریشه بازدید می‌شن.

ترتیب بازدید:
1. زیر درخت چپ
2. زیر درخت راست
3. گره ریشه

مثال:

پیمایش پس‌نورد درخت بالا به این صورت خواهد بود: 4, 5, 2, 3, 1

پیاده‌سازی:

def postorder_traversal(node):
    if node:
        postorder_traversal(node.left)
        postorder_traversal(node.right)
        print(node.value, end=' ')

4. پیمایش سطح به سطح (Level-order Traversal) 📊

در این روش، گره‌ها به ترتیب سطح از بالا به پایین و از چپ به راست بازدید می‌شن. این روش اغلب با استفاده از یک صف (Queue) پیاده‌سازی می‌شه.

ترتیب بازدید:
1. سطح اول (گره ریشه)
2. سطح دوم (گره‌های فرزند)
3. سطح سوم و ...

مثال:

پیمایش سطح به سطح درخت بالا به این صورت خواهد بود: 1, 2, 3, 4, 5

پیاده‌سازی:

from collections import deque

def level_order_traversal(root):
    if not root:
        return
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        print(node.value, end=' ')
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

در این پارت، با چهار روش اصلی پیمایش درخت‌ها آشنا شدیم و هر کدوم رو با مثال‌ها و پیاده‌سازی‌های مختلف بررسی کردیم. این روش‌ها برای کار با درخت‌ها بسیار مهم هستن و در خیلی از الگوریتم‌های پیشرفته استفاده می‌شن. در پارت بعدی، با درخت‌های جستجوی دودویی (BST) آشنا خواهیم شد. همراه ما باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #پیمایش_درخت #درخت_دودویی #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۴: درخت‌های جستجوی دودویی (Binary Search Trees - BST) 🔍🌲

توی پارت قبلی، روش‌های پیمایش درخت‌ها رو بررسی کردیم. امروز می‌خوایم با یکی از مهم‌ترین و کاربردی‌ترین نوع درخت‌ها یعنی درخت‌های جستجوی دودویی (Binary Search Trees - BST) آشنا بشیم. این نوع درخت به شما اجازه می‌ده تا داده‌ها رو به صورت کارآمد ذخیره و جستجو کنید. بیایید شروع کنیم! 🚀

درخت جستجوی دودویی (BST) چیست؟ 🤔

یک درخت جستجوی دودویی یک نوع خاص از درخت‌های دودویی است که ویژگی‌های خاصی داره:

1. هر گره دارای یک مقدار (Value) است.
2. تمام گره‌های زیر درخت چپ دارای مقادیری کمتر از مقدار گره ریشه هستند.
3. تمام گره‌های زیر درخت راست دارای مقادیری بزرگتر یا مساوی مقدار گره ریشه هستند.
4. هر زیر درخت خودش یک درخت جستجوی دودویی است.

این ویژگی‌ها باعث می‌شه که عملیات جستجو، درج و حذف در BST به طور کارآمدی انجام بشه.

مزایای استفاده از BST 🌟

- جستجوی سریع: درخت جستجوی دودویی به شما این امکان رو می‌ده که در زمان نسبتاً کوتاهی یک مقدار رو پیدا کنید.
- مرتب‌سازی: داده‌ها در BST به صورت مرتب ذخیره می‌شن، بنابراین می‌تونید به راحتی داده‌ها رو به ترتیب بازخوانی کنید.
- انعطاف‌پذیری: می‌تونید داده‌ها رو به سادگی اضافه و حذف کنید.

عملیات روی BST 🛠️

1. درج (Insertion)
برای اضافه کردن یک مقدار جدید به BST:

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

پیاده‌سازی:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(node, value):
    if node is None:
        return Node(value)
    
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    
    return node

2. جستجو (Search)
برای پیدا کردن یک مقدار در BST:

- از گره ریشه شروع می‌کنیم.
- اگر مقدار مورد نظر کمتر از گره ریشه باشه، به زیر درخت چپ می‌ریم.
- اگر بزرگتر باشه، به زیر درخت راست می‌ریم.
- اگر برابر باشه، مقدار پیدا شده.

پیاده‌سازی:

def search(node, value):
    if node is None or node.value == value:
        return node
    
    if value < node.value:
        return search(node.left, value)
    else:
        return search(node.right, value)

3. حذف (Deletion)
حذف یک گره در BST به سه حالت مختلف بستگی داره:

- بدون فرزند: گره به سادگی حذف می‌شه.
- یک فرزند: گره حذف می‌شه و فرزندش جایگزین اون می‌شه.
- دو فرزند: گره حذف می‌شه و کوچکترین مقدار از زیر درخت راست جایگزین اون می‌شه (یا بزرگترین مقدار از زیر درخت چپ).

پیاده‌سازی:

def min_value_node(node):
    current = node
    while current.left:
        current = current.left
    return current

def delete(node, value):
    if node is None:
        return node
    
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        
        temp = min_value_node(node.right)
        node.value = temp.value
        node.right = delete(node.right, temp.value)
    
    return node

پیچیدگی زمانی عملیات در BST ⏱️

- جستجو: O(h)
- درج: O(h)
- حذف: O(h)

در اینجا h ارتفاع درخت است. در حالت عادی، ارتفاع درخت در بدترین حالت می‌تونه برابر تعداد گره‌ها (n) باشه، ولی اگر درخت متوازن باشه، ارتفاع برابر log(n) خواهد بود.

اهمیت تعادل (Balance) در BST ⚖️

اگر BST متوازن نباشه، کارایی اون کاهش پیدا می‌کنه و می‌تونه در بدترین حالت به یک لیست پیوندی تبدیل بشه. در پارت بعدی، به بررسی درخت‌های متوازن (Balanced Trees) می‌پردازیم که این مشکل رو حل می‌کنن.


این هم از بررسی درخت‌های جستجوی دودویی! 🌳 توی این پارت با مفهوم BST و عملیات مختلف روی اون آشنا شدیم. در پارت بعدی، به درخت‌های متوازن خواهیم پرداخت که به بهبود کارایی درخت‌های جستجوی دودویی کمک می‌کنن. با ما همراه باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #درخت_دودویی #BST #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳

پارت ۵: درخت‌های متوازن (Balanced Trees) ⚖️🌲

سلام دوستان! 😊 امروز توی پارت پنجم، یکی از مباحث مهم و پیشرفته درخت‌ها رو بررسی می‌کنیم: درخت‌های متوازن (Balanced Trees). متوازن‌سازی درخت‌ها باعث می‌شه که عملیات‌های جستجو، درج و حذف کارآمدتر باشن و درخت همیشه در بهترین حالت عملکرد باقی بمونه. بیایید شروع کنیم! 🚀

درخت متوازن چیست؟ 🤔

یک درخت متوازن، درختیه که در آن ارتفاع دو زیر درخت چپ و راست هر گره تفاوت زیادی با هم نداشته باشن. به عبارت دیگر، اختلاف ارتفاع زیر درخت‌های چپ و راست یک گره نباید از یک مقدار مشخص (معمولاً ۱) بیشتر باشه. این تعادل باعث می‌شه که ارتفاع درخت تقریباً برابر log(n) باشه که n تعداد گره‌های درخته.

چرا متوازن‌سازی مهم است؟ 🌟

اگر درخت جستجوی دودویی (BST) متوازن نباشه، ممکنه در بدترین حالت به یک لیست پیوندی خطی تبدیل بشه، که در این صورت تمام عملیات‌های درج، جستجو و حذف به O(n) می‌رسن. در حالی که اگر درخت متوازن باشه، این عملیات‌ها به O(log n) کاهش پیدا می‌کنن.

انواع درخت‌های متوازن 🌳

چند نوع درخت متوازن معروف وجود دارن که هر کدوم ویژگی‌ها و الگوریتم‌های خاص خودشون رو دارن:

1. درخت AVL 🌲
- تعریف: درخت AVL یکی از اولین انواع درخت‌های متوازن جستجوگره. این درخت طوری طراحی شده که ارتفاع دو زیر درخت چپ و راست هر گره حداکثر ۱ اختلاف داشته باشه.
- عملیات: وقتی یک گره جدید به درخت اضافه یا از درخت حذف می‌شه، ممکنه تعادل درخت به هم بخوره. برای بازیابی تعادل، از چرخش‌های (Rotations) مختلف استفاده می‌کنیم.
- پیچیدگی زمانی: O(log n) برای درج، جستجو و حذف.

2. درخت Red-Black 🎨⚫
- تعریف: درخت Red-Black نوع دیگه‌ای از درخت‌های متوازنه که در اون هر گره به یکی از دو رنگ قرمز یا سیاه رنگ‌آمیزی می‌شه. این درخت قوانین خاصی داره که باعث می‌شه ارتفاع درخت متوازن باقی بمونه.
- ویژگی‌ها: درخت Red-Black همیشه یک درخت نیمه‌متوازنه که تضمین می‌کنه هیچ مسیری درخت بیش از دو برابر مسیر کوتاه‌ترین مسیر نباشه.
- پیچیدگی زمانی: O(log n) برای تمام عملیات‌ها.

پیاده‌سازی ساده درخت AVL 🛠️

در ادامه، یک پیاده‌سازی ساده از درخت AVL رو بررسی می‌کنیم.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    if not node:
        return 0
    return node.height

def update_height(node):
    node.height = 1 + max(get_height(node.left), get_height(node.right))

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left
    T2 = x.right

    x.right = y
    y.left = T2

    update_height(y)
    update_height(x)

    return x

def rotate_left(x):
    y = x.right
    T2 = y.left

    y.left = x
    x.right = T2

    update_height(x)
    update_height(y)

    return y

def insert(node, value):
    if not node:
        return Node(value)

    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)

    update_height(node)

    balance = get_balance(node)

    if balance > 1:
        if value < node.left.value:
            return rotate_right(node)
        else:
            node.left = rotate_left(node.left)
            return rotate_right(node)

    if balance < -1:
        if value > node.right.value:
            return rotate_left(node)
        else:
            node.right = rotate_right(node.right)
            return rotate_left(node)

    return node

مفهوم چرخش (Rotations) در درخت AVL 🔄

- چرخش به راست (Right Rotation): وقتی یک زیر درخت چپ بیش از حد رشد می‌کنه.
- چرخش به چپ (Left Rotation): وقتی یک زیر درخت راست بیش از حد رشد می‌کنه.
- چرخش دوگانه به راست-چپ و چپ-راست (Left-Right and Right-Left Rotations): برای زمانی که ترکیبی از عدم تعادل در زیر درخت‌ها وجود داره.

این چرخش‌ها کمک می‌کنن که درخت دوباره متوازن بشه و ارتفاع درخت کاهش پیدا کنه.

بررسی پیچیدگی زمانی در درخت‌های متوازن ⏱️

- جستجو: O(log n)
- درج: O(log n)
- حذف: O(log n)

این پیچیدگی‌ها نشان می‌ده که درخت‌های متوازن حتی در بدترین حالت هم عملکرد مناسبی دارن و برای کاربردهای واقعی بسیار مناسب هستن.

این هم از بررسی درخت‌های متوازن! 🌳 توی این پارت با درخت‌های AVL و Red-Black و همچنین چگونگی متوازن‌سازی درخت‌ها آشنا شدیم. در پارت بعدی، یک پروژه عملی رو پیاده‌سازی می‌کنیم تا همه این مفاهیم رو در عمل ببینیم. با ما همراه باشید! 🚀

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #AVL #RedBlack #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری چهارم: درخت‌ها (Trees) 🌳
پارت ۶: پروژه عملی و تمرین 💻🎓

سلام به همه! 😊 توی آخرین پارت از سری چهارم، می‌خوایم یک پروژه عملی رو با هم پیاده‌سازی کنیم که به ما کمک می‌کنه تمام مفاهیمی که توی پارت‌های قبلی یاد گرفتیم رو به کار ببریم. این پروژه می‌تونه درک شما از درخت‌ها، به ویژه درخت‌های دودویی (Binary Trees) و درخت‌های جستجوی دودویی (BST)، رو به طور قابل‌توجهی عمیق‌تر کنه.


پروژه: سیستم مدیریت مخاطبین با استفاده از درخت جستجوی دودویی (BST) 📱📇

در این پروژه، یک سیستم مدیریت مخاطبین (Contact Management System) رو پیاده‌سازی می‌کنیم که به کاربران اجازه می‌ده مخاطبین رو ذخیره، جستجو، حذف و نمایش بدن. برای مدیریت و ذخیره مخاطبین، از درخت جستجوی دودویی (BST) استفاده می‌کنیم. هر مخاطب بر اساس نامش در درخت ذخیره می‌شه.

مرحله ۱: تعریف کلاس‌های اصلی 🛠️

ابتدا یک کلاس برای نمایندگی هر مخاطب و یک کلاس برای درخت جستجوی دودویی ایجاد می‌کنیم.

class Contact:
    def __init__(self, name, phone):
        self.name = name
        self.phone = phone

class TreeNode:
    def __init__(self, contact):
        self.contact = contact
        self.left = None
        self.right = None

class ContactBST:
    def __init__(self):
        self.root = None

مرحله ۲: پیاده‌سازی عملیات درج ➕

برای درج یک مخاطب جدید، باید مکان مناسب رو در درخت پیدا کنیم و مخاطب رو در اونجا اضافه کنیم.

def insert(self, contact):
    if not self.root:
        self.root = TreeNode(contact)
    else:
        self._insert(self.root, contact)

def _insert(self, node, contact):
    if contact.name < node.contact.name:
        if node.left is None:
            node.left = TreeNode(contact)
        else:
            self._insert(node.left, contact)
    else:
        if node.right is None:
            node.right = TreeNode(contact)
        else:
            self._insert(node.right, contact)

مرحله ۳: جستجو در درخت 🔍

حالا باید روشی برای جستجو در بین مخاطبین داشته باشیم. این کار رو با استفاده از نام مخاطب انجام می‌دیم.

def search(self, name):
    return self._search(self.root, name)

def _search(self, node, name):
    if node is None or node.contact.name == name:
        return node
    if name < node.contact.name:
        return self._search(node.left, name)
    return self._search(node.right, name)

مرحله ۴: حذف یک مخاطب 🗑️

برای حذف یک مخاطب، باید سه حالت مختلف رو بررسی کنیم:
1. گره‌ای که حذف می‌شه برگی باشه.
2. گره‌ای که حذف می‌شه یک فرزند داشته باشه.
3. گره‌ای که حذف می‌شه دو فرزند داشته باشه.

def delete(self, name):
    self.root = self._delete(self.root, name)

def _delete(self, node, name):
    if node is None:
        return node

    if name < node.contact.name:
        node.left = self._delete(node.left, name)
    elif name > node.contact.name:
        node.right = self._delete(node.right, name)
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left

        min_larger_node = self._get_min(node.right)
        node.contact = min_larger_node.contact
        node.right = self._delete(node.right, min_larger_node.contact.name)

    return node

def _get_min(self, node):
    current = node
    while current.left is not None:
        current = current.left
    return current

مرحله ۵: نمایش مخاطبین (پیمایش درخت) 📜

برای نمایش همه مخاطبین، از پیمایش میانوند (Inorder Traversal) استفاده می‌کنیم که مخاطبین رو به ترتیب حروف الفبا نمایش می‌ده.

def inorder_traversal(self):
    self._inorder_traversal(self.root)

def _inorder_traversal(self, node):
    if node:
        self._inorder_traversal(node.left)
        print(f"Name: {node.contact.name}, Phone: {node.contact.phone}")
        self._inorder_traversal(node.right)

مرحله ۶: استفاده از سیستم مدیریت مخاطبین 📱

حالا می‌تونیم مخاطبین جدید اضافه کنیم، جستجو کنیم، حذف کنیم و لیست مخاطبین رو نمایش بدیم:

maine__ == "__main__":
    contacts = ContactBST()

ادامه کد بالا...

# افزودن مخاطبین
    contacts.insert(Contact("Alice", "123456789"))
    contacts.insert(Contact("Bob", "987654321"))
    contacts.insert(Contact("Charlie", "555666777"))

    # نمایش مخاطبین
    print("All contacts:")
    contacts.inorder_traversal()

    # جستجو
    print("\nSearching for Bob:")
    found = contacts.search("Bob")
    if found:
        print(f"Found: {found.contact.name} - {found.contact.phone}")
    else:
        print("Contact not found.")

    # حذف
    print("\nDeleting Alice:")
    contacts.delete("Alice")

    # نمایش دوباره مخاطبین
    print("\nAll contacts after deletion:")
    contacts.inorder_traversal()

مرحله ۷: تمرین‌ها 📝

1. افزودن قابلیت به‌روزرسانی: برنامه‌تون رو گسترش بدید تا کاربران بتونن اطلاعات یک مخاطب رو به‌روزرسانی کنن (مثلاً تغییر شماره تلفن).
2. افزودن قابلیت جستجوی فازی: قابلیت جستجوی فازی (Fuzzy Search) رو اضافه کنید تا کاربر بتونه با وارد کردن بخشی از نام، مخاطبین مرتبط رو پیدا کنه.
3. گسترش به درخت متوازن: سیستم مدیریت مخاطبین رو به یک درخت متوازن (مثل AVL یا Red-Black) ارتقا بدید تا عملکرد جستجو و درج بهینه‌تر بشه.


این هم از پروژه عملی پارت آخر! 💻 این پروژه به شما کمک می‌کنه که مفاهیم درخت‌ها رو به خوبی درک کنید و بتونید از اون‌ها در برنامه‌های واقعی استفاده کنید. امیدوارم که از این سری لذت برده باشید و اطلاعات مفیدی کسب کرده باشید! 🎉

[این جا کلیک کن تا بیشتر یاد بگیری]

#درخت #پروژه_پایتون #BST #ساختمان_داده #آموزش_پایتون #برنامه_نویسی

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۱: معرفی گراف‌ها 🌐

سلام به همه! 😊 در این پارت، به بررسی مبانی گراف‌ها می‌پردازیم. گراف‌ها یکی از ساختارهای داده‌ای پیچیده و قدرتمند هستند که در مسائل مختلف برنامه‌نویسی و الگوریتم‌ها کاربردهای فراوانی دارند. بیایید با هم به بررسی مفاهیم پایه و انواع گراف‌ها بپردازیم. 🚀

گراف چیست؟ 🤔

گراف یک ساختار داده‌ای است که شامل مجموعه‌ای از رئوس (Nodes یا Vertices) و یال‌ها (Edges) است. یال‌ها به رئوس متصل می‌شوند و ارتباطات یا روابط بین آن‌ها را نشان می‌دهند. گراف‌ها می‌توانند مدل‌های پیچیده‌تری از داده‌ها را نسبت به دیگر ساختارهای داده‌ای مثل آرایه‌ها و لیست‌های پیوندی ارائه دهند.

مفاهیم پایه 📚

- راس (Vertex): هر یک از نقاط یا گره‌های گراف که ممکن است نماینده اشیاء یا موجودیت‌های مختلف باشد.
- یال (Edge): ارتباط بین دو راس که می‌تواند وزن‌دار یا بدون وزن باشد.

انواع گراف‌ها 🔍

1. گراف‌های بدون جهت (Undirected Graphs) 🌟
- تعریف: در این نوع گراف‌ها، یال‌ها بدون جهت هستند و ارتباط بین دو راس به صورت دوطرفه است. یعنی اگر یالی بین راس ( A ) و راس ( B ) وجود داشته باشد، ارتباط از ( A ) به ( B ) و از ( B ) به ( A ) برقرار است.
- مثال: شبکه‌های اجتماعی، جایی که دوستان دوطرفه هستند.

2. گراف‌های جهت‌دار (Directed Graphs) 🌟
- تعریف: در این گراف‌ها، یال‌ها دارای جهت هستند و ارتباط بین دو راس یک‌طرفه است. یعنی اگر یالی از راس ( A ) به راس ( B ) وجود داشته باشد، ارتباط از ( B ) به ( A ) برقرار نیست.
- مثال: مسیرهای یک نقشه، جایی که مسیرها یک‌طرفه هستند.

3. گراف‌های وزن‌دار (Weighted Graphs) 🌟
- تعریف: در این گراف‌ها، هر یال دارای یک وزن است که می‌تواند نشان‌دهنده هزینه، مسافت یا هر نوع دیگری از مقادیر عددی باشد.
- مثال: نقشه‌های جغرافیایی، جایی که مسافت بین نقاط مختلف اهمیت دارد.

4. گراف‌های بدون وزن (Unweighted Graphs) 🌟
- تعریف: در این گراف‌ها، یال‌ها هیچ وزنی ندارند و تنها وجود یا عدم وجود ارتباط بین رئوس اهمیت دارد.
- مثال: شبکه‌های ارتباطی ساده، جایی که فقط ارتباط وجود یا عدم وجود اهمیت دارد.

5. گراف‌های متصل و غیر متصل 🌟
- گراف متصل: گرافی که در آن از هر راس می‌توان به سایر رئوس دسترسی پیدا کرد.
- گراف غیر متصل: گرافی که برخی از رئوس به یکدیگر متصل نیستند و به چند بخش جداگانه تقسیم می‌شود.

کاربردهای گراف‌ها 🌍

گراف‌ها در مسائل مختلفی کاربرد دارند، از جمله:

- شبکه‌های اجتماعی: مدل‌سازی ارتباطات دوستان و پیوندهای شبکه‌ای.
- نقشه‌های جغرافیایی: نمایندگی مسیرها و نقاط مختلف جغرافیایی.
- مدیریت پروژه: مدل‌سازی و بررسی وابستگی‌ها و مراحلی که باید به ترتیب انجام شوند.

تصویرسازی گراف‌ها 🎨

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


در این پارت، با مفاهیم پایه گراف‌ها و انواع مختلف آن‌ها آشنا شدیم. در پارت بعدی، به بررسی نمایندگی‌های مختلف گراف‌ها و مزایا و معایب هر یک خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#گراف #ساختمان_داده #برنامه_نویسی #آموزش_پایتون #گراف_جهت‌دار #گراف_بدون_جهت #گراف_وزن‌دار

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۲: نمایندگی گراف‌ها 🖼️

سلام به همه! 😊 در این پارت، به بررسی نحوه نمایندگی گراف‌ها در حافظه می‌پردازیم. درک نحوه نمایش گراف‌ها به ما کمک می‌کند تا الگوریتم‌ها را به درستی پیاده‌سازی کنیم و عملکرد آن‌ها را بهتر درک کنیم. 🚀


نمایندگی گراف‌ها 📊

برای نمایش گراف‌ها در حافظه، از دو روش اصلی استفاده می‌شود: ماتریس مجاورت (Adjacency Matrix) و لیست مجاورت (Adjacency List). هر کدام از این روش‌ها مزایا و معایب خاص خود را دارند و مناسب استفاده در موقعیت‌های مختلف هستند.

۱. ماتریس مجاورت (Adjacency Matrix) 📐

- تعریف: ماتریس مجاورت یک ماتریس دو بعدی است که در آن هر عنصر ( (i, j) ) نشان‌دهنده وجود یا عدم وجود یال بین راس‌های ( i ) و ( j ) است. برای گراف‌های وزن‌دار، مقدار عنصر ( (i, j) ) وزن یال است و برای گراف‌های بدون وزن، مقدار آن 1 (وجود یال) یا 0 (عدم وجود یال) است.

- مزایا:
- دسترسی سریع: زمان دسترسی به وجود یا عدم وجود یال بین دو راس ( O(1) ) است.
- ساده‌سازی: پیاده‌سازی و درک آن ساده است.

- معایب:
- حافظه زیاد: نیاز به ( O(V^2) ) حافظه دارد، جایی که ( V) تعداد رئوس است، حتی اگر گراف sparse (کم‌درصد یال‌ها) باشد.
- کارایی پایین: برای گراف‌های بزرگ و sparse می‌تواند ناکارآمد باشد.

- نمونه پیاده‌سازی:

    # پیاده‌سازی ماتریس مجاورت برای گراف بدون وزن
    def create_adjacency_matrix(vertices, edges):
        matrix = [[0] * vertices for _ in range(vertices)]
        for u, v in edges:
            matrix[u][v] = 1
            matrix[v][u] = 1  # اگر گراف بدون جهت است
        return matrix
    

۲. لیست مجاورت (Adjacency List) 🗂️

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

- مزایا:
- حافظه کمتر: نیاز به ( O(V + E) ) حافظه دارد، جایی که ( E ) تعداد یال‌ها است. برای گراف‌های sparse، حافظه بهینه‌تری نسبت به ماتریس مجاورت استفاده می‌کند.
- عملکرد بهتر برای گراف‌های بزرگ: کارایی بهتر در اضافه کردن یا حذف یال‌ها و پیمایش یال‌ها.

- معایب:
- دسترسی کمتر سریع: زمان دسترسی به وجود یال بین دو راس ( O(V) ) می‌تواند باشد، که ممکن است برای گراف‌های بزرگ کند باشد.
- پیاده‌سازی پیچیده‌تر: مدیریت و پیاده‌سازی آن پیچیده‌تر از ماتریس مجاورت است.

- نمونه پیاده‌سازی:

    # پیاده‌سازی لیست مجاورت برای گراف بدون وزن
    def create_adjacency_list(vertices, edges):
        adj_list = [[] for _ in range(vertices)]
        for u, v in edges:
            adj_list[u].append(v)
            adj_list[v].append(u)  # اگر گراف بدون جهت است
        return adj_list
    

نمودار نمونه 🖼️

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

  A B C D
  A 0 1 0 1
  B 1 0 1 0
  C 0 1 0 1
  D 1 0 1 0
  

- لیست مجاورت:

  A: [B, D]
  B: [A, C]
  C: [B, D]
  D: [A, C]
  

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

(برای بیشتر یاد گفتن اینجا کلیک کن)

#گراف #نمایندگی_گراف #ماتریس_مجاورت #لیست_مجاورت #برنامه_نویسی #آموزش_پایتون #ساختمان_داده

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۳: الگوریتم‌های جستجو در گراف‌ها 🔍

سلام به همه! 🌟 در این پارت، به بررسی دو الگوریتم اصلی جستجو در گراف‌ها می‌پردازیم: جستجوی عمق‌اول (DFS) و جستجوی پهنای‌اول (BFS). این الگوریتم‌ها ابزارهای اساسی برای پیمایش و تحلیل گراف‌ها هستند. 🚀

الگوریتم‌های جستجو در گراف‌ها 🧩

۱. جستجوی عمق‌اول (Depth-First Search - DFS) 🌲

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

- ویژگی‌ها:
- پیاده‌سازی: می‌تواند با استفاده از پشته یا بازگشت پیاده‌سازی شود.
- کاربردها: یافتن مسیرها، بررسی اتصال، الگوریتم‌های بازیابی، و حل معماها.

- پیاده‌سازی DFS:

  def dfs(graph, start, visited=None):
      if visited is None:
          visited = set()
      visited.add(start)
      print(start)
      for neighbor in graph[start]:
          if neighbor not in visited:
              dfs(graph, neighbor, visited)
      return visited
  

- مثال:

برای گراف زیر:

  A -- B -- C
  |    |
  D -- E
  

اجرای dfs(graph, 'A') ممکن است ترتیب زیر را چاپ کند: A, B, C, E, D.

۲. جستجوی پهنای‌اول (Breadth-First Search - BFS) 🌐

- تعریف: الگوریتم جستجوی پهنای‌اول برای پیمایش گراف به روش سطح‌محور عمل می‌کند. این الگوریتم از یک گره شروع کرده و به ترتیب به گره‌های همسایه آن سطح به سطح جستجو می‌کند.

- ویژگی‌ها:
- پیاده‌سازی: با استفاده از صف پیاده‌سازی می‌شود.
- کاربردها: یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن، الگوریتم‌های بهینه‌سازی، و حل معماهای جغرافیایی.

- پیاده‌سازی BFS:

  from collections import deque

  def bfs(graph, start):
      visited = set()
      queue = deque([start])
      while queue:
          vertex = queue.popleft()
          if vertex not in visited:
              print(vertex)
              visited.add(vertex)
              queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
      return visited
  

- مثال:

برای همان گراف:

  A -- B -- C
  |    |
  D -- E
  

اجرای bfs(graph, 'A') ممکن است ترتیب زیر را چاپ کند: A, B, D, C, E.

مقایسه DFS و BFS 🔍

- DFS:
- مزایا: می‌تواند مسیرهای طولانی و پیچیده را سریعاً پیدا کند.
- معایب: ممکن است گراف‌های بزرگ را به صورت عمیق جستجو کند و به حافظه زیادی نیاز داشته باشد.

- BFS:
- مزایا: مناسب برای یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن.
- معایب: ممکن است حافظه بیشتری نسبت به DFS نیاز داشته باشد به دلیل ذخیره‌ی تمام گره‌های سطحی.


در این پارت، الگوریتم‌های جستجو در گراف‌ها یعنی DFS و BFS را بررسی کردیم. در پارت بعدی، به الگوریتم‌های جستجوی کوتاه‌ترین مسیر در گراف‌ها خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#جستجوی_عمق_اول #جستجوی_پهنای_اول #DFS #BFS #گراف #برنامه_نویسی #آموزش_پایتون #ساختمان_داده

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۴: الگوریتم‌های کوتاه‌ترین مسیر 🛤️

سلام به همه! 🌟 در این پارت، به بررسی دو الگوریتم مهم برای پیدا کردن کوتاه‌ترین مسیر در گراف‌ها خواهیم پرداخت: الگوریتم دیکسترا (Dijkstra) و الگوریتم فلوید-وارشال (Floyd-Warshall). این الگوریتم‌ها در مسائل مختلف مسیریابی و تحلیل گراف کاربرد دارند. 🚀

الگوریتم‌های کوتاه‌ترین مسیر 🧭

۱. الگوریتم دیکسترا (Dijkstra’s Algorithm) 🚗

- تعریف: الگوریتم دیکسترا برای یافتن کوتاه‌ترین مسیر از یک گره مبدأ به تمام گره‌های دیگر در گراف‌های وزن‌دار و غیرمنفی طراحی شده است. این الگوریتم از گره مبدأ شروع کرده و مسیرهای کوتاه‌ترین فاصله را به گره‌های دیگر محاسبه می‌کند.

- ویژگی‌ها:
- محدودیت: فقط برای گراف‌های با وزن‌های غیرمنفی مناسب است.
- پیاده‌سازی: می‌تواند با استفاده از ساختار داده‌های مختلف مانند صف اولویت یا بنیاد هِپ پیاده‌سازی شود.

- پیاده‌سازی دیکسترا:

  import heapq

  def dijkstra(graph, start):
      # Initialize distances and priority queue
      distances = {vertex: float('infinity') for vertex in graph}
      distances[start] = 0
      priority_queue = [(0, start)]

      while priority_queue:
          current_distance, current_vertex = heapq.heappop(priority_queue)

          # Nodes can only be added once to the priority queue
          if current_distance > distances[current_vertex]:
              continue

          for neighbor, weight in graph[current_vertex].items():
              distance = current_distance + weight

              # Only consider this new path if it's better
              if distance < distances[neighbor]:
                  distances[neighbor] = distance
                  heapq.heappush(priority_queue, (distance, neighbor))

      return distances
  

- مثال:

برای گراف زیر:

  A --(1)-- B --(4)-- C
  |         |
  (2)       (6)
  |
  D
  

اجرای dijkstra(graph, 'A') ممکن است فواصل کوتاه‌ترین مسیر از A به سایر گره‌ها را به صورت زیر ارائه دهد:
- A → B: 1
- A → C: 7
- A → D: 2

۲. الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm) 🌐

- تعریف: الگوریتم فلوید-وارشال برای پیدا کردن کوتاه‌ترین مسیر بین تمام جفت گره‌ها در گراف‌های وزن‌دار (چه مثبت و چه منفی) طراحی شده است. این الگوریتم قادر است ماتریس کوتاه‌ترین مسیرها را برای تمامی جفت گره‌ها محاسبه کند.

- ویژگی‌ها:
- محدودیت: می‌تواند با وزن‌های منفی کار کند اما نباید دورهای منفی وجود داشته باشد.
- پیاده‌سازی: با استفاده از ماتریس پیاده‌سازی می‌شود.

- پیاده‌سازی فلوید-وارشال:

  def floyd_warshall(graph):
      # Initialize distances
      vertices = list(graph.keys())
      distances = {vertex: {v: float('infinity') for v in vertices} for vertex in vertices}
      
      for u in vertices:
          distances[u][u] = 0
          for v, weight in graph[u].items():
              distances[u][v] = weight

      # Compute shortest paths
      for k in vertices:
          for i in vertices:
              for j in vertices:
                  if distances[i][j] > distances[i][k] + distances[k][j]:
                      distances[i][j] = distances[i][k] + distances[k][j]

      return distances
  

- مثال:

برای همان گراف:

  A --(1)-- B --(4)-- C
  |         |
  (2)       (6)
  |
  D
  

اجرای floyd_warshall(graph) ممکن است ماتریس کوتاه‌ترین مسیرها را به صورت زیر تولید کند:
- A → B: 1
- A → C: 7
- A → D: 2

مقایسه دیکسترا و فلوید-وارشال ⚖️

- دیکسترا:
- مزایا: سریع‌تر برای گراف‌های بزرگ و فقط یک منبع.
- معایب: تنها برای گراف‌های غیرمنفی مناسب است.

- فلوید-وارشال:
- مزایا: مناسب برای گراف‌هایی با وزن‌های منفی و برای یافتن کوتاه‌ترین مسیرها بین تمام جفت گره‌ها.
- معایب: کندتر برای گراف‌های بسیار بزرگ به دلیل پیچیدگی زمانی (O(V^3)).

در این پارت، الگوریتم‌های دیکسترا و فلوید-وارشال را بررسی کردیم. در پارت بعدی، به بررسی الگوریتم‌های درخت‌های پوشا خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

#الگوریتم_دیکسترا #الگوریتم_فلوید_وارشال #کوتاه‌ترین_مسیر #گراف #برنامه_نویسی #آموزش_پایتون #ساختمان_داده

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۵: الگوریتم‌های درخت‌های پوشا (Minimum Spanning Tree) 🌳

سلام به همه! 🌟 در این پارت، به بررسی دو الگوریتم مهم برای یافتن درخت پوشای کمینه (Minimum Spanning Tree - MST) در گراف‌ها خواهیم پرداخت: الگوریتم کرُسکل (Kruskal) و الگوریتم پرایم (Prim). این الگوریتم‌ها در مسائل مختلفی مانند طراحی شبکه و بهینه‌سازی ساختارها کاربرد دارند. 🚀

الگوریتم‌های درخت‌های پوشا کمینه (MST) 🌟

۱. الگوریتم کرُسکل (Kruskal’s Algorithm) 🌲

- تعریف: الگوریتم کرُسکل برای یافتن درخت پوشای کمینه در یک گراف وزن‌دار طراحی شده است. این الگوریتم از انتخاب یال‌های کمترین وزن و افزودن آن‌ها به درخت تا زمانی که همه گره‌ها پوشش داده شوند، استفاده می‌کند.

- ویژگی‌ها:
- روش: گراف را با یال‌های وزن‌دار مرتب می‌کند و یال‌ها را به ترتیب اضافه می‌کند تا یک درخت پوشا کمینه تشکیل شود.
- پیاده‌سازی: با استفاده از ساختار داده‌ی مجموعه‌های پیشرفته (Union-Find) برای جلوگیری از ایجاد حلقه‌ها (Cycles).

- پیاده‌سازی کرُسکل:

  class UnionFind:
      def __init__(self, n):
          self.parent = list(range(n))
          self.rank = [0] * n

      def find(self, u):
          if self.parent[u] != u:
              self.parent[u] = self.find(self.parent[u])
          return self.parent[u]

      def union(self, u, v):
          rootU = self.find(u)
          rootV = self.find(v)
          if rootU != rootV:
              if self.rank[rootU] > self.rank[rootV]:
                  self.parent[rootV] = rootU
              elif self.rank[rootU] < self.rank[rootV]:
                  self.parent[rootU] = rootV
              else:
                  self.parent[rootV] = rootU
                  self.rank[rootU] += 1

  def kruskal(vertices, edges):
      union_find = UnionFind(len(vertices))
      mst = []
      edges = sorted(edges, key=lambda x: x[2])

      for u, v, weight in edges:
          if union_find.find(u) != union_find.find(v):
              union_find.union(u, v)
              mst.append((u, v, weight))

      return mst
  

- مثال:

برای گراف با یال‌ها و وزن‌های زیر:

  A --(1)-- B
  |         |
  (3)       (4)
  |
  C
  

اجرای kruskal(vertices, edges) ممکن است درخت پوشای کمینه به شکل زیر باشد:
- A → B با وزن 1
- A → C با وزن 3

۲. الگوریتم پرایم (Prim’s Algorithm) 🌳

- تعریف: الگوریتم پرایم برای یافتن درخت پوشای کمینه از یک گره شروع می‌کند و به تدریج یال‌های کمترین وزن را به درخت اضافه می‌کند تا تمامی گره‌ها به درخت اضافه شوند.

- ویژگی‌ها:
- روش: از یک گره شروع می‌کند و یال‌های کمترین وزن را به درخت اضافه می‌کند تا همه گره‌ها پوشش داده شوند.
- پیاده‌سازی: با استفاده از داده‌های ساختار اولویت برای انتخاب یال‌های کمترین وزن.

- پیاده‌سازی پرایم:

  import heapq

  def prim(graph, start):
      mst = []
      visited = set()
      min_heap = [(0, start)]
      total_weight = 0

      while min_heap:
          weight, u = heapq.heappop(min_heap)
          if u in visited:
              continue

          visited.add(u)
          total_weight += weight
          if weight > 0:
              mst.append((prev, u, weight))

          for v, w in graph[u].items():
              if v not in visited:
                  heapq.heappush(min_heap, (w, v))
                  prev = u

      return mst, total_weight
  

- مثال:

برای همان گراف:

  A --(1)-- B
  |         |
  (3)       (4)
  |
  C
  

اجرای prim(graph, 'A') ممکن است درخت پوشای کمینه به شکل زیر باشد:
- A → B با وزن 1
- A → C با وزن 3

مقایسه کرُسکل و پرایم ⚖️

- کرُسکل:
- مزایا: مناسب برای گراف‌های پراکنده با تعداد یال‌های کم.
- معایب: پیچیدگی در استفاده از Union-Find.

- پرایم:
- مزایا: مناسب برای گراف‌های چگال با تعداد یال‌های زیاد.
- معایب: نیاز به استفاده از ساختار داده‌های اولویت.


در این پارت، الگوریتم‌های کرُسکل و پرایم را بررسی کردیم. در پارت بعدی، به بررسی پروژه‌های عملی و تمرین‌ها برای تثبیت مفاهیم خواهیم پرداخت. با ما همراه باشید! 🚀

(برای بیشتر یاد گفتن اینجا کلیک کن)

سری پنجم: گراف‌ها (Graphs) 🕸️
پارت ۶: تمرین و پروژه عملی 🚀

سلام به همه! 🌟 در این پارت، به پیاده‌سازی یک پروژه عملی و حل تمرین‌ها برای تثبیت مفاهیم گراف‌ها خواهیم پرداخت. این تمرینات به شما کمک می‌کند تا مفاهیم یادگرفته شده را به صورت عملی پیاده‌سازی کنید و درک عمیق‌تری از گراف‌ها پیدا کنید.

پروژه عملی: مسیریابی در نقشه 🗺️

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

مراحل پروژه:

1. تعریف گراف:
- مدل‌سازی نقشه به عنوان گراف با گره‌ها (مکان‌ها) و یال‌ها (مسیرها).
- هر یال دارای وزن خواهد بود که نشان‌دهنده طول یا هزینه مسیر است.

2. پیاده‌سازی نمایندگی گراف:
- استفاده از لیست مجاورت برای نمایندگی گراف.
- تعریف کلاس برای گراف و اضافه کردن گره‌ها و یال‌ها.

   class Graph:
       def __init__(self):
           self.graph = {}

       def add_vertex(self, vertex):
           if vertex not in self.graph:
               self.graph[vertex] = {}

       def add_edge(self, u, v, weight):
           if u not in self.graph:
               self.add_vertex(u)
           if v not in self.graph:
               self.add_vertex(v)
           self.graph[u][v] = weight
           self.graph[v][u] = weight  # برای گراف بدون جهت
   

3. پیاده‌سازی الگوریتم‌های مسیریابی:
- استفاده از الگوریتم دیکسترا برای یافتن کوتاه‌ترین مسیر بین دو نقطه.
- پیاده‌سازی الگوریتم دیکسترا:

   import heapq

   def dijkstra(graph, start):
       distances = {vertex: float('infinity') for vertex in graph.graph}
       distances[start] = 0
       priority_queue = [(0, start)]

       while priority_queue:
           current_distance, u = heapq.heappop(priority_queue)

           if current_distance > distances[u]:
               continue

           for neighbor, weight in graph.graph[u].items():
               distance = current_distance + weight

               if distance < distances[neighbor]:
                   distances[neighbor] = distance
                   heapq.heappush(priority_queue, (distance, neighbor))

       return distances
   

4. اجرای پروژه:
- تعریف گراف با مکان‌ها و مسیرها.
- یافتن کوتاه‌ترین مسیر بین دو نقطه با استفاده از الگوریتم دیکسترا.

   # تعریف گراف
   g = Graph()
   g.add_edge('A', 'B', 1)
   g.add_edge('A', 'C', 4)
   g.add_edge('B', 'C', 2)
   g.add_edge('B', 'D', 5)
   g.add_edge('C', 'D', 1)

   # یافتن کوتاه‌ترین مسیر از 'A' به سایر نقاط
   distances = dijkstra(g, 'A')
   print(distances)
   

5. نتیجه‌گیری:
- بررسی نتایج و تحلیل عملکرد الگوریتم.
- افزودن قابلیت‌های اضافی مانند نمایش مسیر کوتاه‌تر.


تمرین‌های تکمیلی ✏️

1. مسئله کوتاه‌ترین مسیر:
- پیاده‌سازی الگوریتم فلوید-وارشال برای یافتن همه‌به‌همه مسیرها در گراف.

2. مدیریت شبکه اجتماعی:
- طراحی سیستمی برای مدیریت شبکه اجتماعی با قابلیت‌های جستجو و نمایش روابط بین کاربران با استفاده از گراف.

3. گراف‌های جهت‌دار:
- پیاده‌سازی و تحلیل الگوریتم‌های جستجو و مسیریابی برای گراف‌های جهت‌دار.


با تکمیل این پروژه و تمرین‌ها، درک شما از گراف‌ها و الگوریتم‌های آن‌ها بهبود خواهد یافت. برای هر سوال یا نیاز به راهنمایی بیشتر، خوشحال می‌شویم که کمک کنیم. موفق باشید! 🌟

(برای بیشتر یاد گفتن اینجا کلیک کن)

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

سری پنجم از آموزش ساختمان داده (گراف ها)(graphs)☝️☝️