الرسوم

التعريف

الـ graph هو هيكل رياضي يُستخدم لتمثيل العلاقات بين عناصر منفصلة تُسمّى vertices. العلاقة الواحدة تُسمّى edge، وهي تعبّر عن أن زوجًا من الـ vertices مرتبطان ببعض.

مثال: المدن والطرق

مثال كلاسيكي على الـ graph هو شبكة مدن مرتبطة بطرق. تخيّل عدة مدن في دولة، بعض أزواج المدن بينهم طرق، والبعض الآخر لا. إذا كنت تخطط للسفر من المدينة \(A\) إلى المدينة \(B\)، قد تحتاج تمرّ على مدينة أو أكثر كمدن وسيطة في الطريق.

ليش نستخدم Graphs؟

تمثيل المسائل على شكل graphs يسمح لنا بحلّها بكفاءة باستخدام خوارزميات الرسوم البيانية، مثل:

• “هل ممكن نوصل من المدينة \(A\) إلى المدينة \(B\)؟”
• “وش أقصر مسار من المدينة \(A\) إلى المدينة \(B\)؟”

تخزين أنواع مختلفة من Graphs

فيه أنواع متعددة من graphs، وفيه طرق مختلفة لتخزين كل نوع. بنناقش الأنواع اللي غالبًا تظهر في المسائل، وطرق تخزينها.

الأنواع

الاتجاه (Direction)

أحيانًا الـ edges يكون لها اتجاه، وهذا يعني أن edge \((U, V)\) و edge \((V, U)\) مختلفين. غالبًا يُذكر هذا في نص المسألة بمصطلحات مثل unidirectional أو directed، بينما مصطلحات مثل bidirectional و undirected تعني أن الـ edges ما لها اتجاه معيّن.

الأوزان (Weights)

في بعض الـ graphs، الـ edges (وأحيانًا الـ vertices) يكون مرتبط فيها قيمة أو أكثر. مثال على ذلك إننا نعطي مدة زمنية للطرق في مثال المدن والطرق. ممكن نقول إن edge \((U, V, W)\) يعني أن السفر على الطريق بين المدينتين \(U\) و \(V\) يحتاج وقت مقداره \(W\).

Note

لاحظ أن في الصياغة \((U, V, W)\) ما تم ذكر اتجاه محدد للـ edge، لذلك نقدر نفترض أنها undirected.

التخزين

قبل ما نتكلم عن طرق التخزين، بنناقش بعض الاستعلامات (queries) اللي ممكن نسويها، واللي بتساعدنا نقارن بين طرق التخزين المختلفة ونفهم نقاط القوة والضعف لكل وحدة.

• كم التعقيد المكاني (space complexity) لهذه الطريقة؟
• كم التعقيد الزمني (time complexity) للتحقق إذا كانت الـ edge \((U, V)\) موجودة؟
• إذا كان عندنا vertex معيّن \(U\)، كم التعقيد الزمني للمرور على كل الـ vertices \(V\) المجاورة له؟

لازم أيضًا نفهم كيف يُعطى لنا الـ graph في مدخلات المسألة. الطريقة الأكثر شيوعًا هي أننا نقرأ أولًا \(N\) و \(M\)، حيث يمثلان عدد الـ vertices وعدد الـ edges على الترتيب، ثم في كل واحد من الأسطر الـ \(M\) التالية يُعطى زوج أعداد صحيحة \(U\) \(V\) (وأحيانًا وزن \(W\)). هذا يعني أن فيه edge بين الـ vertices \(U\) و \(V\) (وإذا كان الـ graph موجه فعادة يكون من \(U\) إلى \(V\) إلا إذا ذُكر غير ذلك).

Tip

نوصي أنك تطلع على الموقع التالي: Graph Editor

وأخيرًا، من أفضل الممارسات إننا نخلي كل الحاويات (containers) المتعلقة بالـ graph معرفة بشكل global. السبب أن أغلب خوارزميات الرسوم البيانية يُفضّل تنفيذها باستخدام دوال (functions)، ويكون الوصول للـ graph أسهل إذا كان global. لذلك مهم جدًا تعرف القيود (constraints) على متغيرات مثل \(N\) و \(M\) عشان تضبط أحجام الحاويات بشكل صحيح وتتجنب الوصول خارج الحدود (out of bounds).

Caution

هنا نفترض أن الـ graph ما يحتوي على multiple edges، يعني ما فيه زوج vertices مرتبطين مباشرة بأكثر من edge واحدة.

Array of Edges

هذه أبسط طريقة لتخزين الـ edges. بما أن الـ edges تُعطى على شكل قائمة أزواج، بنخزنها مباشرة في array من أزواج.

const int maxN = 100'000;
const int maxM = 200'000;

pair<int,int> E[maxM];

int main () {
    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < m ; i++) {
        int u, v; cin >> u >> v;
        E[i] = {u, v};
    }
}

Note

في حالة الـ weighted graphs نقدر نعرّف struct يحتوي القيم الثلاث \(3\) أو نستخدم std::tuple أو std::array. عمومًا يُفضّل نتجنب nesting للـ pairs.

Category	Complexity
Space	\(O(M)\)
Checking if an edge exists	\(O(M)\)
Looping over neighbors of a vertex	\(O(M)\)

Adjacency List

في هذه الطريقة ننشئ \(N\) قوائم، كل وحدة عبارة عن vector، بحيث أن القائمة رقم \(i_{th}\) تخزن كل الجيران (neighbors) للـ vertex رقم \(i\).

const int maxN = 100'000;
const int maxM = 200'000;

vector<int> adjacency_list[maxN + 1]; // زدنا واحد لأن غالبًا الـ vertices تبدأ من 1 (1-indexed)

int main () {
    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < m ; i++) {
        int u, v; cin >> u >> v;
        adjacency_list[u].push_back(v); // أضف v إلى جيران u
        adjacency_list[v].push_back(u); // إذا كان undirected، نضيف u إلى قائمة v كذلك
    }
}

Note

في حالة الـ weighted graphs نقدر نستخدم vector<pair<int,int>> بحيث \((V, W)\) تعني أن \(V\) جار والـ edge له وزن \(W\).

Category	Complexity
Space	\(O(M)\)
Checking if an edge exists	\(O(K)\) حيث \(K\) هو عدد الجيران
Looping over neighbors of a vertex	\(O(K)\) حيث \(K\) هو عدد الجيران

Tip

مع أن المرور على الجيران يبدو بطيء، إلا أنه فعليًا يساوي \(O(M)\) إذا جمعنا على كل الـ vertices.

WarningChallenge

هل تقدر تعدّل هذا الـ container بحيث تسرّع عملية “checking if an edge exists” بدون ما تأثر على باقي الاستعلامات؟

Adjacency Matrix

هذه الطريقة تنشئ مصفوفة بحجم \(N \times N\) من القيم المنطقية (booleans) اسمها \(G\)، بحيث أن \(G_{i,j}\) تساوي true إذا كان الـ vertex رقم \(i\) متصل مباشرة بالـ vertex رقم j، و false في غير ذلك.

const int maxN = 1'000;
const int maxM = 200'000;

bool G[maxN + 1][maxN + 1] // زدنا واحد لأن غالبًا الـ vertices تبدأ من 1 (1-indexed)

int main () {
    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < m ; i++) {
        int u, v; cin >> u >> v;
        G[u][v] = true;
        G[v][u] = true; // إذا كان الـ graph غير موجه لازم نكتب هذا السطر كذلك
    }
}

Note

في حالة الـ weighted graphs، بدل ما تكون قيم منطقية، ممكن \(G_{i, j}\) تكون عدد صحيح يمثل وزن الـ edge من \(i\) إلى \(j\)، لكن انتبه لكيف تميّز بين الـ edges غير الموجودة.

Category	Complexity
Space	\(O(N^2)\)
Checking if an edge exists	\(O(1)\)
Looping over neighbors of a vertex	\(O(N)\)