آموزش الگوریتم های تئوری گراف تجسم شدند

سرفصل ها و درس ها

معرفی Introduction

• مقدمه ای بر نظریه گراف Introduction to graph theory

• [مهم] قبل از شروع [IMPORTANT] Before we start

• اصطلاحات و انواع نمودارها Terminology and types of graphs

• آزمون: اصطلاحات و انواع نمودارها Quiz: Terminology and types of graphs

نمایش نمودار Graph representation

• نمایندگی لیست مجاورت Adjacency list representation

• نمایش ماتریس مجاورت Adjacency matrix representation

• لیست مجاورت در مقابل ماتریس مجاورت Adjacency list vs adjacency matrix

• امتحان: لیست ها و ماتریس های مجاورت Quiz: Adjacency lists and matrices

پیمایش نمودار Graph traversal

• الگوریتم جستجوی اول عمق (DFS). Depth-first search (DFS) algorithm

• مشکل: مسیر در یک نمودار وجود دارد Problem: Path exists in a graph

• راه حل: مسیر در یک نمودار وجود دارد Solution: Path exists in a graph

• الگوریتم جستجوی عرض اول (BFS). Breadth-first search (BFS) algorithm

• مشکل: حداقل لبه ها از ابتدا تا انتها Problem: Minimum edges from start to end

• راه حل: حداقل لبه ها از ابتدا تا انتها Solution: Minimum edges from start to end

• DFS و BFS در نمودارهای ضمنی DFS and BFS in implicit graphs

• آزمون: DFS و BFS Quiz: DFS and BFS

مرتب سازی توپولوژیکی Topological sort

• مرتب سازی توپولوژیکی چیست؟ What is topological sort?

• الگوریتم مرتب سازی توپولوژیکی مبتنی بر DFS DFS-based topological sort algorithm

• الگوریتم مرتب سازی توپولوژیکی مبتنی بر BFS (الگوریتم کان) BFS-based topological sort algorithm (Kahn's algorithm)

• مشکل: همه دستور العمل های ممکن را پیدا کنید Problem: Find all possible recipes

• راه حل: تمام دستور العمل های ممکن را پیدا کنید Solution: Find all possible recipes

• مسابقه: مرتب سازی توپولوژیکی Quiz: Topological sort

مشکل کوتاه ترین مسیر Shortest path problem

• مقدمه ای بر مسئله کوتاه ترین مسیر Introduction to the shortest path problem

• الگوریتم دایکسترا Dijkstra's algorithm

• الگوریتم بلمن-فورد Bellman-Ford algorithm

• الگوریتم فلوید-وارشال Floyd-Warshall algorithm

• الگوریتم جانسون Johnson's algorithm

• کوتاه ترین مسیر در نمودارهای بدون وزن Shortest path in unweighted graphs

• کوتاه ترین مسیر در گراف های غیر چرخه ای جهت دار Shortest path in directed acyclic graphs

• الگوریتم A* A* algorithm

• راه حل: ارزان ترین پروازها در عرض k توقف Solution: Cheapest flights within k stops

• امتحان: مشکل کوتاه ترین مسیر Quiz: Shortest path problem

درختان Trees

• درخت چیست؟ What is a tree?

• خارج از درخت (درختی) و تبدیل نمودار به خارج از درخت Out-trees (arborescence) and graph to out-tree conversion

• مشکل: همه گره ها k در یک درخت فاصله دارند Problem: All nodes distance k in a tree

• راه حل: همه گره ها از k در یک درخت فاصله دارند Solution: All nodes distance k in a tree

• امتحان: درخت چیست؟ Quiz: What is a tree?

حداقل درختان پوشا Minimum spanning trees

• درخت پوشا (حداقل) چیست؟ What is a (minimum) spanning tree?

• الگوریتم پریم Prim's algorithm

• الگوریتم کروسکال Kruskal's algorithm

• مشکل: حداقل هزینه برای اتصال همه نقاط Problem: Min cost to connect all points

• راه حل: حداقل هزینه برای اتصال همه نقاط مشکل Solution: Min cost to connect all points problem

• امتحان: حداقل درختان پوشا Quiz: Minimum spanning trees

مسیرها/چرخه های اویلرین و همیلتونی Eulerian and Hamiltonian paths/cycles

• مسیر/چرخه اویلری چیست؟ What is a Eulerian path/cycle?

• الگوریتم هیرهولزر Hierholzer's algorithm

• مشکل: برنامه سفر را بازسازی کنید Problem: Reconstruct itinerary

• راه حل: برنامه سفر را بازسازی کنید Solution: Reconstruct itinerary

• مسیر/چرخه همیلتونی چیست؟ What is a Hamiltonian path/cycle?

• الگوریتم ردیابی چرخه هامیلتونی Hamiltonian cycle finding backtracking algorithm

• مسابقه: مسیرها/چرخه‌های اویلرین و همیلتونی Quiz: Eulerian and Hamiltonian paths/cycles

برش و اتصال Cuts and connectivity

• معرفی Introduction

• الگوریتم ترجان برای یافتن SCC Tarjan's algorithm for finding SCCs

• الگوریتم کوساراجو برای یافتن SCC Kosaraju's algorithm for finding SCCs

• الگوریتم یافتن نقاط بیان Articulation points finding algorithm

• راه حل: حداقل روز برای قطع اتصال جزیره Solution: Minimum days to disconnect island

• امتحان: برش و اتصال Quiz: Cuts and connectivity

رنگ آمیزی نمودار Graph coloring

• مقدمه ای بر رنگ آمیزی نمودار Introduction to graph coloring

• بررسی رنگ پذیری 2 (گراف دوبخشی) Checking 2-colorability (bipartite graph)

• بررسی رنگ پذیری k با بک ترک Checking k-colorability with backtracking

• رنگ آمیزی حریص Greedy coloring

• اکتشافی (ولش پاول، DSatur) Heuristics (Welsh-Powell, DSatur)

• مشکل: حل کننده سودوکو Problem: Sudoku solver

• راه حل: بیایید یک حل کننده سودوکو بسازیم Solution: Let's make a Sudoku solver

• امتحان: رنگ آمیزی نمودار Quiz: Graph coloring

مشکل فروشنده دوره گرد Traveling Salesman Problem

• مقدمه ای بر مسئله فروشنده دوره گرد Introduction to Traveling Salesman Problem

• نیروی بی رحم و راه حل عقب نشینی برای TSP Brute force and backtracking solution for TSP

• راه حل برنامه نویسی پویا برای TSP Dynamic programming solution for TSP

• الگوریتم Nearest Neighbor و الگوریتم Sorted Edges Nearest Neighbor algorithm and Sorted Edges algorithm

• الگوریتم کریستوفیدس Christofides algorithm

• مشکل: یافتن کوتاهترین ابر رشته (LeetCode #943) Problem: Find the shortest superstring (LeetCode #943)

• راه حل: کوتاه ترین ابررشته را پیدا کنید (LeetCode #943) Solution: Find the shortest superstring (LeetCode #943)

• امتحان: مشکل فروشنده دوره گرد Quiz: Traveling Salesman Problem

مشکل حداکثر جریان Maximum flow problem

• معرفی Introduction

• الگوریتم فورد-فولکرسون Ford-Fulkerson algorithm

• الگوریتم ادموندز-کارپ Edmonds-Karp algorithm

• الگوریتم دینیک Dinic's algorithm

• الگوریتم هاپکرافت-کارپ (تطبیق دو بخشی بدون وزن) Hopcroft-Karp algorithm (unweighted bipartite matching)

• مشکل: حداکثر دانش آموزانی که در امتحان شرکت می کنند (LeetCode #1349) Problem: Maximum students taking exam (LeetCode #1349)

• راه حل: حداکثر دانش آموزان در امتحان (LeetCode #1349) Solution: Maximum students taking exam (LeetCode #1349)

• آزمون: مشکل حداکثر جریان Quiz: Maximum flow problem

مشکلات را تمرین کنید Practice problems

• مشکل: کلیدها و اتاق ها (LeetCode #841) Problem: Keys and rooms (LeetCode #841)

• راه حل: کلیدها و اتاق ها (LeetCode #841) Solution: Keys and rooms (LeetCode #841)

• مشکل: پوسیدگی پرتقال (LeetCode #994) Problem: Rotting oranges (LeetCode #994)

• راه حل: پوسیدگی پرتقال (LeetCode #994) Solution: Rotting oranges (LeetCode #994)

• مشکل: مسیر رنگ متناوب (LeetCode #1129) Problem: Alternating color path (LeetCode #1129)

• راه حل: مسیر رنگ متناوب (LeetCode #1129) Solution: Alternating color path (LeetCode #1129)

• مشکل: مجموع فواصل در درخت (LeetCode #834) Problem: Sum of distances in tree (LeetCode #834)

• راه حل: مجموع فواصل در درخت (LeetCode #834) Solution: Sum of distances in tree (LeetCode #834)

• مشکل: مسیرهای محدود به طول لبه (LeetCode #1697) Problem: Edge length limited paths (LeetCode #1697)

• راه حل: مسیرهای محدود به طول لبه (LeetCode #1697) Solution: Edge length limited paths (LeetCode #1697)

پروژه: مولد ماز و حل کننده Project: Maze generator and solver

• یک پیچ و خم ایجاد کنید Generate a maze

• حل یک پیچ و خم Solve a maze