پیاده سازی گراف¶

گراف را چگونه به ما ورودی می دهند؟¶

یک روش استاندارد ورودی دادن گراف که در سوال های المپیاد معمولا از آن استفاده می کنند، به این صورت است که در خط اول تعداد راس ها و تعداد یال ها را به شما ورودی می دهند و در ادامه به تعداد یال ها، در هر خط شماره دو راس سر و ته آن یال را می نویسند. برای مثال

5 6
1 2
1 3
1 4
2 5
4 5
3 4

یک گراف ۵ راسی و ۶ یالی است و مثلا درجه راس شماره ۴ برابر ۳ است. با استفاده از برنامه وب https://csacademy.com/app/graph_editor/ می توانید گراف بالا را به صورت گرافیکی مشاهده کنید.

لیست پیوندی¶

اگر چه می توانیم گراف را به صورت آرایه ای از یال ها ذخیره کنیم، اما این ذخیره سازی مناسب نیست. زیرا اگر بخواهیم به همسایه های یک راس دسترسی داشته باشیم، باید تمام یال ها را پیمایش کنیم و این در بسیاری از استفاده ها، قابل قبول نیست.

یک روش بهتر، لیست پیوندی است. منظور از لیست پیوندی، لیستی است که پیوند ها (راس های همسایه که با یال به این راس پیوند دارند) را نگه می دارد. در این روش ما برای هر راس یک آرایه با اندازه متغیر یا همان وکتور در سی پلاس پلاس نگه می داریم و لیست همسایه های هر راس را درون آن می ریزیم. کد این روش به شکل زیر خواهد شد:

const int M = 1e5 + 5; // bishine tedad rase momken ke dar soal maloom mishavad

vector<int> list_peyvandi[M];

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i += 1) {
    int u, v;
    cin >> u >> v;
    list_peyvandi[u].push_back(v);
    list_peyvandi[v].push_back(u);
  }
}

مزایای این روش این است که اولا می شود با مرتبه زمانی درجه یک راس، همسایه های آن را پیمود و دوم این که حافظه و زمان اجرای آن از \(O(N+E)\) است. (دقت کنید که در فصل قبل خواندیم که جمع درجات تمامی رئوس دو برابر تعداد یال ها است) این زمان خطی بهترین پیچیدگی ای است که می توان به دست آورد چون خود عملیات ورودی گرفتن همین قدر طول می کشد.

به دست آوردن اطلاعات مفید از گراف¶

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

const int M = 1e5 + 5; // bishine tedad rase momken ke dar soal maloom mishavad

vector <int> list_peyvandi[M];

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i += 1) {
    int u, v;
    cin >> u >> v;
    list_peyvandi[u].push_back(v);
    list_peyvandi[v].push_back(u);
  }
  int dmin = M + 5;
  int dmax = -1;
  for (int u = 1; u <= n; u += 1) {
    cout << "Rase shomare: " << u << "\n";
    int d = list_peyvandi[u].size();
    cout << "Daraje: " << d << "\n";
    if (dmin > d) dmin = d;
    if (dmax < d) dmax = d;
    cout << "Hamsaye ha: ";
    for (int v: list_peyvandi[u]) {
      cout << v << " ";
    }
    cout << "\n";
  }
  cout << "Delta koochak: " << dmin << "\n";
  cout << "Delta bozorg: " << dmax << "\n";
}

اطلاعات جانبی¶

این مساله را در نظر بگیرید: یک باغ داریم که چند درخت دارد و درخت ها هر کدام با جاده به درخت های دیگر وصل هستند. (در فضای خالی علف هست و فقط از جاده ها می شود رفت) زمان پیموده شدن هر جاده و تعداد سیب های هر درخت را می دانیم. می خواهیم در k دقیقه بیشترین سیب ممکن را بچینیم. ورودی به صورت گراف، می تواند به شکل زیر باشد. اول تعداد رئوس (n)، یال ها (m) و وقتی که داریم (k) در خط اول داده می شود. در خط بعدی n عدد که تعداد سیب های هر درخت و در m خط بعد در هر خط سه عدد که به ترتیب شماره ابتدا، انتها و زمان مورد نیاز جاده است. پس یک مثال می تواند مثال زیر باشد:

5 6 43.2
1 2 100 5 3
1 2 20
1 3 3.5
1 4 7.1
2 5 100.2
4 5 31
3 4 1.1

ما در این قسمت به راه حل بهینه این مساله نمی پردازیم، بلکه هدف ما بررسی نحوه ورودی گرفتن این گراف و ذخیره آن در یک لیست پیوندی است. روشی که در بالا گفتیم، یک ایراد دارد و آن این است که زمان هر یال را از دست می دهد و نمی تواند در جایی ذخیره کند. برای رفع این مشکل، به جای ذخیره راس های همسایه در لیست پیوندی، شماره یال را نگه داریم و برای هر یال، دو سر آن و زمان آن را در آرایه نگه داریم. تنها نکته ای که باید به آن توجه کرد، این است که به ازای هر راس نمی دانیم که این راس به عنوان سر یال ذخیره شده است یا به عنوان ته یال و این به دست آوردن سر دیگر یال را کمی سخت می کند. یک راه حل این است که دو سر یال را جمع بزنیم و از راس فعلی کم کنیم. چون یکی از آن ها همان راس فعلی است، سر دیگر یال به دست می آید. یک راه دیگر این است که دو سر یال و راس فعلی را با هم ایکس اور کنیم که چون ایکس اور هر عددی با خودش برابر صفر است، مثل حالت چمع و تفریق، سر دیگر به دست می آید. ایکس اور در کامپیوتر ها اندکی سریع تر است اما اگر عملیات های بیتی را بلد نیستید یا با آن ها حال نمی کنید، از همان روش جمع و تفریق استفاده کنید. در کد زیر از ایکس اور استفاده کرده ایم.

const int Mras = 1e5 + 5; // bishine tedad rase momken ke dar soal maloom mishavad
const int Myal = 3e5 + 5; // bishine tedad yale momken ke dar soal maloom mishavad

vector<int> list_peyvandi[Mras];
int sib[Mras];
int u[Myal], v[Myal];
double zaman[Myal];

int main() {
  int n, m;
  cin >> n >> m;
  for (int e = 1; e <= m; e += 1) { // e shomare yal ast
    int x, y;
    cin >> x >> y;
    list_peyvandi[x].push_back(e); // deghat konid ke ba bala fargh darad
    list_peyvandi[y].push_back(e); // shomare yal rikhte shode
  }
  // dar edame hamsaye haye har ras raa chap mikonim
  for (int x = 1; x <= n; x += 1) {
    cout << "Rase shomare: " << x << "\n";
    cout << "Hamsaye ha: \n";
    for (int e: list_peyvandi[x]) {
      int y = u[e] ^ v[e] ^ x; // be dast avardane sare digar
      //  y = u[e] + v[e] - x; ham mishod
      //  y = u[e] == x ? v[e] : u[e]; ham mishod
      cout << "  hamsaye = " << y << ", zaman = " << zaman[e] << "\n";
    }
  }
}

یک الگوریتم واقعی¶

به عنوان پایان این بخش می خواهیم از چیزی که یاد گرفتیم استفاده کنیم. این راه حل برای مساله بالا را در نظر بگیرید: هر مرحله کوتاه ترین یالی که سیب هایش را نچیده ایم را می پیماییم تا زمانی که وقتمان تمام شود یا به یک راس برسیم که همه سیب های همسایه هایش چیده شده باشند. خوب است قبل از دیدن کد، خودتان تلاش کنید تا آن را پیاده کنید.

const int Mras = 1e5 + 5; // bishine tedad rase momken ke dar soal maloom mishavad
const int Myal = 3e5 + 5; // bishine tedad yale momken ke dar soal maloom mishavad

vector <int> list_peyvandi[Mras];
int sib[Mras];
int u[Myal], v[Myal];
double zaman[Myal];
bool chide[Mras];

int main() {
  int n, m;
  cin >> n >> m;
  for (int e = 1; e <= m; e += 1) { // e shomare yal ast
    int x, y;
    cin >> x >> y;
    list_peyvandi[x].push_back(e); // deghat konid ke ba bala fargh darad
    list_peyvandi[y].push_back(e); // shomare yal rikhte shode
  }
  // liste peyvandi ra bar hasbe zaman moratab mikonim
  for (int x = 1; x <= n; x += 1) {
    // sort yeki az por karbord tarin tabe haye c++ ast. agar
    // balad nistid beravid yaad begirid
    sort(list_peyvandi[x].begin(), list_peyvandi[x].end(), [](int a, int b) {
      // in yek lambda function ast ke jozve ghabeliat haye c++14 ast.
      // agar balad nistid, mitavaanid be saadegi in taabe raa
      // baalaa tarif konid yaa in ke beravid yaad begirid
      return zaman[a] < zaman[b];
    });
  }
  int cur = 1; // rase mabda raa ras 1 dar nazar migirim
  int score = 0; // sib haye chide shode in ja zakhire mishavand
  while (k > 0) {
    chide[cur] = true;
    score += sib[cur];
    bool berim = false;
    int koja = -1;
    for (int e: list_peyvandi[cur]) {
      int nxt = u[e] ^ v[e] ^ cur;
      if (chide[nxt]) continue;
      if (zaman[e] > k) break;
      berim = true;
      koja = nxt;
      k -= zaman[e];
      break;
    }
    if (!berim) break;
    cur = koja;
  }
  cout << score;
}

توجه کنید که این راه حل صرفا یک راه حل حریصانه است و یک راه حل بهینه نیست. برای تمرین می توانید خودتان یک مثال بزنید که این کد رفتار بهینه ای نشان نمی دهد و بهترین جواب را به دست نمی آورد.

اما به هر حال، این کد قدرت لیست پیوندی را نشان می دهد. پیچیدگی زمانی کد بالا \(O(n+mlg(m))\) است اما بدون لیست پیوندی به سختی می توانستید با زمان بهتر از \(O(nm)\) این الگوریتم را پیاده سازی کنید.