This wiki has no edits or logs made within the last 45 days, therefore it is marked as inactive. If you would like to prevent this wiki from being closed, please start showing signs of activity here. If there are no signs of this wiki being used within the next 15 days, this wiki may be closed per the Dormancy Policy. This wiki will then be eligible for adoption by another user. If not adopted and still inactive 135 days from now, this wiki will become eligible for deletion. Please be sure to familiarize yourself with Miraheze's Dormancy Policy. If you are a bureaucrat, you can go to Special:ManageWiki and uncheck "inactive" yourself. If you have any other questions or concerns, please don't hesitate to ask at Stewards' noticeboard.

مولفه های همبندی

از shaazzz
پرش به ناوبری پرش به جستجو

یک گراف بدون جهت با n راس و m یال داریم و وظیفه ما پیدا کردن مولفه های همبندی این گراف است. در گراف های بدون جهت ۲ راس متعلق به یک مولفه همبندی هستند اگر و تنها اگر یک مسیر بین آن ها با استفاده از یال های این گراف باشد و هیچ مسیری هم بین دو مولفه همبندی متفاوت وجود ندارد. این مساله در گراف جهت دار را مولفه های قویا همبند می گویند که می توانید توضیح آن را در بخش بعدی بخوانید.

+ برای حل کردن این مساله هم می توانیم از BFS و هم می توانیم از DFS استفاده کنیم. در واقع باید دنباله ای از DFS ها را روی گراف اجرا کرد :

   اولین DFS را روی یکی از رئوس گراف مانند v اجرا می کنیم و با این کار تمام رئوس متعلق به اولین مولفه همبندی پیدا خواهند شد.
   سپس اولین راس از رئوس باقی مانده که دیده نشده (mark[u]=false) پیدا می کنیم و روی آن هم DFS می زنیم. 
   بدین ترتیب رئوس متعلق به دومین مولفه همبندی هم پیدا می شود و همین کار را ادامه می دهیم تا جایی که هیچ راسی که دیده نشده است، باقی نماند.

اردر این الگوریتم از (O(n+m است. چون هیچ راسی دو بار دیده نمی شود و این بدین معنی است که هر یال دقیقا دو بار طی می شود (دیده می شود). یک بار از یک سر آن و بار دیگر از آن سرش.

int n;
vector<int> g[MAXN] ;
bool used[MAXN] ;
vector<int> comp ;

void dfs(int v) {
    used[v] = true ;
    comp.push_back(v);
    for (size_t i = 0; i < (int) g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to])
            dfs(to);
    }
}

void find_comps() {
    for (int i = 0; i < n ; ++i)
        used [i] = false;
    for (int i = 0; i < n ; ++i)
        if (!used[i]) {
            comp.clear();
            dfs(i);
            cout << "Component:" ;
            for (size_t j = 0; j < comp.size(); ++j)
                cout << ' ' << comp[j];
            cout << endl ;
        }
}
  • مهم ترین تابعی که در این کد استفاده شده است مربوط به تابع ()find_comps است که مولفه های همبندی گراف را پیدا کردیم و نمایش می دهد.
  • لیست همسایگی راس های گراف به عنوان ورودی داده شده است و [g[i شامل همسایه های راس i است.
  • MAXN مساوی حداکثر تعداد رئوس گراف است. ( معمولا MAXN را بیشتر از این حداکثر مقدار می گیرند : MAXN = n + 10 )
  • وکتور [comp[i شامل رئوسی است که در مولفه همبندی i ام وجود دارند.

مسائل تمرینی[ویرایش]