====== مرتب‌سازی توپولوژیک ====== ===== تعریف ===== مرتب‌سازی توپولوژیک، مرتب سازی رئوس یک گراف جهت‌دار بدون طوقه و بدون دور است به طوری که هر راس قبل از رئوسی میاید که به آنها یال خروجی داده‌است. ===== الگوریتم ===== ==== شرح ==== برای مرتب‌سازی گراف روی گراف [[جست‌وجوی عمق‌اول|پیمایش عمق‌اول]] می‌زنیم به هر راسی که رسیدیم آنرا علامت می‌زنیم. هنگام خروج از آن راس یک علامت دیگر به معنی پایان بررسی آن راس روی آن می‌زنیم و آنرا در پشته‌‌ای می‌ریزیم که جواب مسئله یعنی رئوس مرتب شده است. حال اگر به راسی رسیدیم که علامت وارد شدن به آن بود ولی علامت پایان نداشت یعنی که در گراف دور وجود دارد و مرتب‌سازی ممکن نیست. سپس روی بقیه رئوسی که علامت نخورده‌اند پیمایش انجام می‌دهیم ولی وارد راس‌هایی که علامت دارند نمی‌شویم. دست آخر رئوس داخل پشته را یکی یکی بیرون می‌آوریم و چاپ می‌کنیم. ==== صحت الگوریتم ===== اگر گراف دور داشته باشد، الگوریتم آنرا تشخیص می‌دهد و مرتب‌سازی را ادامه نمی‌دهد. راس $u$ اگر قبل از راس $v$ وارد پشته شود به این معنی است که یالی از $u$ به $v$ وجود ندارد، پس مشکلی وجود ندارد که راس $v$ قبل از $u$ در مرتب سازی قرار بگیرد. ===== پیچیدگی‌ الگوریتم ===== پیچیدگی الگوریتم برایر [[جست‌وجوی عمق‌اول|الگوریتم پیمایش عمق‌اول]] یعنی $O(v+e)$ که $v$ برابر تعداد رئوس و $e$ تعداد یال‌هاست. ===== الگوریتم کان ===== توضیحات مربوط به الگوریتم $Kahn$ را می‌توانید در [[تست_غیردوری_بودن_گراف_جهت‌دار#الگوریتم_کان|بخش تست غیردوری بودن گراف جهت‌دار]] ببنید. ===== پیاده‌سازی اولیه ===== #include #include #include using namespace std; const int N=1000; // حداکثر تعداد رئوس int n, m; // تعداد رئوس و تعداد یال‌های جهت دار vector g[N]; // برای هر راس یک پشته که شامل راس‌هایی که به آنها یال خروجی دارد bool used[N]; bool end[N]; vector ans; bool dfs (int v) { used[v] = true; for (int i=0; i> n>>m; for(int i=0; i>t>>r; g[--t].push_back(--r); // است n-1 از ورودی یکی کم می‌کنیم چون بازه‌ی معتبر ما از صفر تا } if (topological_sort()) for(int i=n-1; i>=0; i--) cout << ans[i]+1 < ===== مراجع ===== * [[http://e-maxx.ru/algo/topological_sort|مرتب‌سازی توپولوژیک - سایت ماکزیمال]] * [[http://en.wikipedia.org/wiki/Topological_sorting|مرتب‌سازی توپولوژیک - ویکی‌پدیا]]