Topological Sort ترتیبی میسازد که تمام dependencyهای یک DAG رعایت شوند. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Topological Sorting زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
اگر B به A وابسته باشد، A باید قبل از B قرار گیرد. Kahn این کار را با indegree انجام میدهد.
مراحل اجرا
- indegree همه رأسها را حساب میکنیم.
- رأسهای indegree صفر را وارد Queue میکنیم.
- هر رأس را برداشته و indegree همسایهها را کم میکنیم.
- اگر همه پردازش نشوند، cycle وجود دارد.
نمونه کد JavaScript
function topoSort(graph) {
const indegree = {};
for (const u of Object.keys(graph)) indegree[u] ??= 0;
for (const u of Object.keys(graph))
for (const v of graph[u]) indegree[v] = (indegree[v] ?? 0) + 1;
const q = Object.keys(indegree).filter(x => indegree[x] === 0), out = [];
while (q.length) {
const u = q.shift(); out.push(u);
for (const v of graph[u] ?? []) if (--indegree[v] === 0) q.push(v);
}
return out.length === Object.keys(indegree).length ? out : null;
}مثالهای واقعی و دنیای کار
- ترتیب Build Packageها
- Prerequisite درسها
- CI/CD Jobs
- Workflow و ETL
پیچیدگی زمانی و فضایی
O(V + E) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
Dependencyهای جهتدار بدون چرخه
چه زمانی مناسب نیست؟
در گراف دارای cycle ترتیب توپولوژیک کامل نداریم.
جمعبندی
Topological Sorting را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.