تشخیص دور داشتن گراف جهت دار

مقدمه

در بخش های قبلی, گاهی لازم می‌شد تشخیص دهیم یک گراف جهت‌دار دور دارد یا خیر! برای مثال برای اینکه یک ترتیب توپولوژیک از گراف ارائه دهیم, ابتدا باید مطمئن شویم گراف بدون دور است. زیرا گرافی که دور دارد, هیچ ترتیب توپولوژیکی ندارد!

در اینجا به شرح دو الگوریتم می‌پردازیم که می‌توانند دوری بودن گراف را تشخیص دهند. از طرفی در الگوریتم اول, یک دور در گراف خروجی می‌دهیم!

الگوریتم پیدا کردن دور با استفاده از DFS

شرح: این الگوریتم مشابه با الگوریتم بخش 3.3 می‌باشد با این تفاوت که در اینجا برای هر راس دو نوع علامت‌گذاری خواهیم داشت. به این صورت که گراف را با استفاده از \(DFS\) پیمایش می‌کنیم و هر راس را هنگامی که به آن وارد می‌شویم، به عنوان یک راس دیده شده و زمانی که از آن راس خارج می‌شویم، به عنوان یک راسی که از آن خارج شده‌ایم، علامت‌گذاری می‌کنیم. حال اگر در زمان پیمایش به راسی برسیم که از آن را دیده‌ایم ولی از آن خارج نشده‌ایم، به این نتیجه می‌رسیم که گراف دور دارد و در غیر این صورت گراف بدون دور است.

اثبات درستی: زمانی که در حال پیمایش گراف هستیم، اگر در راسی مانند \(v\) قرار داشتیم و به راسی مانند \(u\) رسیدیم که آن را دیده‌ایم ولی همچنان از آن خارج نشده‌ایم، این به این معناست که یالی جهت‌دار از \(v\) به \(u\) وجود دارد و \(u\) مسیری جهت‌دار به \(v\) دارد که در این صورت گراف دور خواهد داشت. همچنین اگر گراف دور داشته باشد، این الگوریتم حتما آن را پیدا خواهد کرد، زیرا در غیر این صورت اگر فرض کنیم \(G\) گرافی با حداقل یک دور باشد که الگوریتم دور را در آن پیدا نکرده باشد، اگر \(v\) اولین راسی باشد که از دور \(C\) به آن وارد شده‌ایم و \(e\) یالی از \(u\) به \(v\) باشد که در دور \(C\) قرار دارد، در این صورت در پیمایش، قبل از خارج شدن از \(v\) به \(u\) می‌رسیم (زیرا این دو راس در یک دور هستند و حتما از \(v\) به \(u\) مسیر هست) و با استفاده از یال \(e\) دوباره به \(v\) می‌رسیم که یعنی دور پیدا کرده‌ایم. پس از تناقض حاصل نتیجه می‌شود که الگوریتم دور را در هر گرافی که دور دارد، پیدا می‌کند.

اگه اینترنت یارو آشغال باشه این میاد

پیچیدگی الگوریتم

در الگوریتم یک بار از \(DFS\) استفاده کردیم که در نتیجه پیچیدگی آن برابر با \(O(m+n)\) است که \(n\) تعداد راس‌ها و \(m\) تعداد یال‌ها می‌باشد.

پیاده‌سازی الگوریتم

توجه کنید که در پیاده‌سازی زیر در صورت داشتن دور، دور پیدا شده و در صورت نداشتن دور، ترتیب توپولوژیک راس‌ها را خروجی می‌دهیم.

#include<bits/stdc++.h>

using namespace std;

const int MX=5e5+200;

int n, m;
vector<int> gr[MX], topo, cycle;
bool st[MX], ed[MX];

bool dfs(int v){
    st[v]=1;
    for(int u: gr[v]){
        if(st[u] && !ed[u]){
            cycle.push_back(u);
            cycle.push_back(v);
            return 0;
        }
        if(!st[u] && !dfs(u)){
            if(cycle[0]!=cycle[cycle.size()-1])
                cycle.push_back(v);
            return 0;
        }
    }
    ed[v]=1;
    topo.push_back(v);
    return 1;
}

int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int v,u;
        cin>>v>>u;
        gr[v].push_back(u);
    }
    bool check=1;
    for(int i=0; i<n; i++){
        if(!st[i] && !dfs(i)){
            check=0;
            break;
        }
    }
    if(check){
        cout<<"no cycle \ntopo order: ";
        for(int v: topo){
            cout<<v<<' ';
        }
    }
    else{
        cout<<"cycle: ";
        for(int i=cycle.size()-2; i>=0; i--){
            cout<<cycle[i]<<' ';
        }
    }
    return 0;
}

الگوریتم کان (kahn)

شرح: روش دیگری برای فهمیدن اینکه یک گراف دور دارد یا نه, الگوریتم کان است. این الگوریتم بر پایه استقرا عمل می‌کند. این روش با قضیه 3.3.2 بسیار شبیه می‌باشد!

الگوریتم به اینصورت است که در ابتدا یک مجموعه خالی از راس ها داریم که آن را \(zero\) می‌نامیم. این مجموعه, مجموعه راس هایی هست که در گراف کنونی درجه ورودی‌شان 0 است.

در ابتدا, راس هایی که درجه ورودی‌شان 0 است را به \(zero\) اضافه می‌کنیم.

در هر مرحله, مجموعه راس هایی که در \(zero\) هستند را به همراه یال‌هایشان از گراف حذف می‌کنیم و به دنبال این‌کار, ممکن است یک سری راس جدید درجه ورودی‌شان 0 شود و به \(zero\) اضافه شوند. این‌کار را آنقدر ادامه می‌دهیم تا یا تعداد راس های گراف برابر با 0 شود و یا اینکه مجموعه \(zero\) خالی شود.

اگر در یک مرحله اندازه مجموعه \(zero\) برابر با 0 بود و گراف کنونی هنوز شامل تعدادی راس بود, آنگاه گراف حتما دور دارد و اگر این اتفاق نیفتاد و همه راس ها از گراف حذف شدند, آنگاه گراف دور ندارد.

اگه اینترنت یارو آشغال باشه این میاد

برای درک بهتر, شکل۲ را ببینید. در این شکل, دور آبی رنگ هیچگاه به مجموعه \(zero\) وارد نمی‌شود و بنابراین گراف دوری تشخیص داده می‌شود!

اثبات درستی: برای اثبات الگوریتم دو حالت از گراف را در نظر می‌گیریم. ابتدا فرض کنید گراف \(G\) دور داشته باشد, آنگاه ادعا می‌کنیم الگوریتم به درستی دور داشتن را تشخیص می‌دهد.

اگر \(G\) دور داشته باشد, آنگاه اگر این دور را \(C\) بنامیم, هیچکدام از راس های \(C\) هیچگاه به \(zero\) اضافه نمی‌شوند(چرا؟). پس به جایی می‌رسیم که گراف هنوز شامل تعدادی راس است, اما \(zero\) خالی است! پس الگوریتم دور داشتن را تشخیص می‌دهد.

حال اگر گراف دور نداشته باشد, با استقرا روی تعداد راس ها ثابت می‌کنیم که همه راس ها حذف می‌شوند!

اولا که اگر گراف دور نداشته باشد, طبق قضیه 3.1.3 تعداد راس در گراف \(G\) هستند که دردجه ورودی‌شان 0 است. پس این راس ها به مجموعه \(zero\) اضافه می‌شوند, سپس به همراه یال‌هایشان از گراف حذف می‌شوند. پس تعداد راس ها کم شد. از طرفی شرایط استقرا برقرار است و گراف کنونی دور ندارد. پس طبق استقرا همه راس ها از گراف حذف ‌می‌شوند و الگوریتم به درستی دور نداشتن را تشخیص می‌دهد.

پیچیدگی الگوریتم

برای بررسی پیچیدگی الگوریتم, باید ببینیم که روی راس ها و یال ها چه مقدار پیمایش کردیم. ما زمانی روی یال ها پیمایش می‌کنیم که راسی در مجموعه \(zero\) باشد, آنگاه روی یال های مجاور آن راس پیمایش می‌کنیم. از طرفی هر راس فقط یکبار در \(zero\) می‌آید و پس از آن از گراف حذف می‌شود. پس ما روی هر یال یکبار پیمایش میکنیم.

از طرفی هنگامی روی راس ها پیمایش میکنیم که راس در مجموعه \(zero\) قرار گیرد. و مشابها, هر راس فقط یک بار به این مجموعه اضافه می‌شود و پس از آن از گراف حذف می‌شود.

پس پیچیدگی الگوریتم بالا برابر است با \(O(n + m)\) است که مشابه با الگوریتم قبلی است!

پیاده‌سازی الگوریتم

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 5;

int n, m; // tedad ras ha va yal ha
int in_edge[maxn]; // in_edge[v] daraje vorodi rase v hast!

vector<int> g[maxn]; // vector e mojaverat
vector<int> zero; // ras haie ke daraje vorodi 0 daran va baiad hazf shan!

bool has_cycle(){
      for(int i = 0; i < n; i++){
            if(in_edge[i] == 0){
                  zero.push_back(i);
            }
      }

      for(int i = 0; i < n; i++) {
            if(zero.size() == 0){
                  return true;
            }

            int v = zero[zero.size() - 1]; // ozve akhar az remove_set
            zero.pop_back();

            for(int u : g[v]){
                  in_edge[u]--;
                  if(in_edge[u] == 0){
                        zero.push_back(u);
                  }
            }
      }

      return false;
}


int main(){
      cin >> n >> m;
      for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v; // u, v 0-based hastan
            g[u].push_back(v);
            in_edge[v]++; // yale (u, v) dar graph ast. pas daraje vorodi v yeki ziad mishe!
      }

      if(has_cycle()){
            cout << "graph has at least one cycle!" << endl;
      } else {
            cout << "graph is acyclic!" << endl;
      }

      return 0;
}