نقاط برشی
Articulation Pointsنقاط برشی یک الگوریتم از دسته گراف‌ها است. این الگوریتم روی Nodeها و Edgeهای گراف کار می‌کند و معمولاً به representation مثل adjacency list/matrix و stateهایی مثل visited، distance، parent یا indegree نیاز دارد.
اول این مفهوم را در ذهن نگه دار
نقاط برشی یک الگوریتم از دسته گراف‌ها است. این الگوریتم روی Nodeها و Edgeهای گراف کار می‌کند و معمولاً به representation مثل adjacency list/matrix و stateهایی مثل visited، distance، parent یا indegree نیاز دارد.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم نقاط برشی ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای نقاط برشی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای نقاط برشی در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
نقاط برشی چه مسئله‌ای را حل می‌کند؟
نقاط برشی یک الگوریتم از دسته گراف‌ها است. این الگوریتم روی Nodeها و Edgeهای گراف کار می‌کند و معمولاً به representation مثل adjacency list/matrix و stateهایی مثل visited، distance، parent یا indegree نیاز دارد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.