האם הגרף דו-צדדי?
שיעור 14 מתוך 14 בקורס גרפים – סדרת מבני נתונים מס' 9 של Coddy.
גרף הוא דו־חלקי אם אפשר לפצל את הקודקודים שלו לשתי קבוצות כך שכל קשת תחבר קודקוד בקבוצה אחת לקודקוד בקבוצה השנייה. חשבו על אדום וכחול: לכל קשת יש קצה אדום אחד וקצה כחול אחד.
BFS מספק בדיקה פשוטה. מתחילים בכל קודקוד, צובעים אותו באדום ומתקדמים החוצה. כל שכן חדש מקבל צבע הפוך לצבע של הקודקוד שממנו הגענו. אם נתקלים בקשת שמחברת שני קודקודים בעלי אותו צבע, הגרף אינו דו־חלקי. הדוגמה הקלאסית היא מעגל באורך אי־זוגי: משולש 0-1-2-0 מאלץ את קודקוד 0 להיות אדום וגם כחול.
חשוב לזכור: אם לגרף יש כמה רכיבים קשירים, צריך להתחיל צביעה חדשה בשני צבעים בכל אחד מהם. התבנית הפשוטה ביותר היא לולאה יחידה על כל הקודקודים, שמפעילה BFS בכל פעם שהיא מוצאת קודקוד שלא נצבע.
אתגר
קלכתבו פונקציה isBipartite שמקבלת מערך int דו־ממדי adjacency ומערך int vertices, ומחזירה true אם הגרף דו־צדדי, ו־false אחרת.
בנו את הגרף (הוסיפו כל קודקוד באמצעות addVertex, ואז כל קשת באמצעות addEdge). לאחר מכן צבעו בשני צבעים באמצעות BFS בכל רכיב קשירות: הקצו לצומת ההתחלה את הצבע 0, ותנו לכל שכן את הצבע 1 - color[u]. אם תמצאו קשת ששני הקצוות שלה כבר צבועים באותו צבע, החזירו false. אחרת, החזירו true.
חובה להשתמש במחלקה Graph (שסופקה בקובץ graph) — אל תשתמשו במבנים המובנים של השפה (מפות, קבוצות) כדי לייצג את רשימת השכנויות. נתוני עזר עבור האלגוריתם (מפת צבעים, תור) יכולים להשתמש בטיפוסים של הספרייה התקנית.
נסו בעצמכם
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}
כל השיעורים ביחידה גרפים – סדרת מבני נתונים מס' 9
תרגלו בעצמכם: קומפיילר C אונליין