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

مقدمه¶

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

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

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

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

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

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\) اضافه می‌شوند, سپس به همراه یال‌هایشان از گراف حذف می‌شوند. پس تعداد راس ها کم شد. از طرفی شرایط استقرا برقرار است و گراف کنونی دور ندارد. پس طبق استقرا همه راس ها از گراف حذف ‌می‌شوند و الگوریتم به درستی دور نداشتن را تشخیص می‌دهد.

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;
}