پرش به محتویات

پیدا کردن رئوس برشی در یک گراف با پیچیدگی $O(N+M)$

یک گراف بدون جهت به ما داده شده است. یک رأس برشی (یا cut vertex) به عنوان رأسی تعریف می‌شود که با حذف آن به همراه یال‌های متصل به آن، گراف ناهمبند می‌شود (یا به طور دقیق‌تر، تعداد مؤلفه‌های همبندی در گراف افزایش می‌یابد). مسئله، پیدا کردن تمام رئوس برشی در گراف داده شده است.

الگوریتم توصیف شده در اینجا بر اساس جستجوی عمق اول است و دارای پیچیدگی زمانی $O(N+M)$ است که در آن $N$ تعداد رئوس و $M$ تعداد یال‌های گراف است.

الگوریتم

یک رأس دلخواه از گراف مانند $root$ را انتخاب کرده و جستجوی عمق اول را از آن اجرا می‌کنیم. به نکته زیر توجه کنید (که اثبات آن ساده است):

  • فرض کنید در حین اجرای DFS، در حال پیمایش یال‌های خروجی از رأس $v \ne root$ هستیم. اگر یال فعلی $(v, to)$ به گونه‌ای باشد که هیچ‌کدام از رأس $to$ یا نوادگان آن در درخت پیمایش DFS، یال برگشتی (back-edge) به هیچ‌یک از اجداد $v$ نداشته باشند، آنگاه $v$ یک رأس برشی است. در غیر این صورت، $v$ رأس برشی نیست.

  • حال حالت باقی‌مانده یعنی $v=root$ را در نظر بگیریم. این رأس یک رأس برشی خواهد بود اگر و تنها اگر بیش از یک فرزند در درخت DFS داشته باشد.

اکنون باید یاد بگیریم که این شرط را برای هر رأس به طور کارآمد بررسی کنیم. ما از «زمان ورود به گره» که توسط جستجوی عمق اول محاسبه می‌شود، استفاده خواهیم کرد.

بنابراین، فرض کنید $tin[v]$ زمان ورود به گره $v$ را نشان دهد. ما آرایه‌ای به نام $low[v]$ معرفی می‌کنیم که به ما امکان می‌دهد این شرط را برای هر رأس $v$ بررسی کنیم. $low[v]$ برابر با کمینه مقدار $tin[v]$، زمان‌های ورود $tin[p]$ برای هر گره $p$ که از طریق یک یال برگشتی $(v, p)$ به گره $v$ متصل است، و مقادیر $low[to]$ برای هر رأس $to$ که فرزند مستقیم $v$ در درخت DFS است، می‌باشد:

$$low[v] = \min \begin{cases} tin[v] \\ tin[p] &\text{ برای تمام رئوس }p\text{ که }(v, p)\text{ یک یال برگشتی است} \\ low[to]& \text{ برای تمام رئوس }to\text{ که }(v, to)\text{ یک یال درختی است} \end{cases}$$

حال، یک یال برگشتی از رأس $v$ یا یکی از نوادگانش به یکی از اجدادش وجود دارد، اگر و تنها اگر رأس $v$ فرزندی مانند $to$ داشته باشد که $low[to] < tin[v]$ برقرار باشد. اگر $low[to] = tin[v]$ باشد، یال برگشتی مستقیماً به $v$ می‌رسد، در غیر این صورت به یکی از اجداد $v$ می‌رسد.

بنابراین، یک رأس $v$ (که ریشه نیست) در درخت DFS یک رأس برشی است اگر و تنها اگر فرزندی مانند to داشته باشد که شرط $low[to] \geq tin[v]$ برای آن برقرار باشد.

پیاده‌سازی

پیاده‌سازی باید بین سه حالت تمایز قائل شود: وقتی در درخت DFS از یک یال به سمت پایین می‌رویم، وقتی یک یال برگشتی به یکی از اجداد رأس پیدا می‌کنیم و وقتی به والد یک رأس برمی‌گردیم. این حالت‌ها عبارتند از:

  • $visited[to] = false$ - یال بخشی از درخت DFS است؛
  • $visited[to] = true$ && $to \neq parent$ - یال، یک یال برگشتی به یکی از اجداد است؛
  • $to = parent$ - یال به والد در درخت DFS برمی‌گردد.

برای پیاده‌سازی این منطق، به یک تابع جستجوی عمق اول نیاز داریم که رأس والدِ گره فعلی را به عنوان ورودی بپذیرد.

int n; // تعداد گره‌ها
vector<vector<int>> adj; // لیست مجاورت گراف

vector<bool> visited;
vector<int> tin, low;
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    int children=0;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] >= tin[v] && p!=-1)
                IS_CUTPOINT(v);
            ++children;
        }
    }
    if(p == -1 && children > 1)
        IS_CUTPOINT(v);
}

void find_cutpoints() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs (i);
    }
}

تابع اصلی find_cutpoints است؛ این تابع مقداردهی‌های اولیه لازم را انجام می‌دهد و جستجوی عمق اول را در هر مؤلفه همبندی گراف آغاز می‌کند.

تابع IS_CUTPOINT(a) تابعی است که این واقعیت را که رأس $a$ یک رأس برشی است پردازش می‌کند، برای مثال، آن را چاپ می‌کند (توجه داشته باشید که این تابع ممکن است برای یک رأس چندین بار فراخوانی شود).

مسائل تمرینی