מטריצת שכנויות בשפת C

[robicon]

אני צריך לבנות עץ מכוון בעל N צמתים שיהיה מיוצג על ידי מטריצת שכנויות בגודל N*N הבעיה של היא שאני צריך לקבל מהמשתמש שני צמתים ולהחזיר TRUE אם קיימת קשת מכוונת בניהם וFALSE אם לא קיימת(ממש כמו עץ בינארי רק שמיוצג על ידי מטריצת שכנויות) ואני לא מוצא דרך לעשות חיפוש כזה באופן יעיל.

יש רעיונות?

תודה

[שניצל]

מה מייצג איבר במטריצה? כלומר, מה המשמעות של הערך במקום i,j?

[robicon]

1 ו0 כאשר 1 מייצג שקיים לו בן ו0 שלא קיים

כאשר המשתמש מכניס את i=האבא ו j=הבן

ואני צריך להחזיר אם יש בין האבא לבן קשת מכוונת זאת אמרת אם הוא באמת אבא שלו

[robicon]

עלי לכתוב פונקציה בשם path המקבלת כפרמטר מטריצת שכנויות A ואינדקסים של שני צמתים u ו v ומחזירה TRUE אם ורק אם קייםמסלול מכוון(לפי כיווני החצים) מצומת u לצומת v ,בעץ המיוצג על ידי מטריצה A. אחרת היא מחזירה FALSE

[שניצל]

אה, עכשיו זה יותר ברור. כי מקודם אמרת שצריך לבדוק האם קיימת קשת מכוונת, לא מסלול...

תבדיל אגב בין בן (child) לצאצא (descendent). בן זה אומר בן ישיר (כלומר יש קשת מכוונת ביניהם), צאצא זה אומר עקיף (כלומר יש מסלול מכוון ביניהם). בדיוק כמו שאתה צאצא של סבא שלך, ולא בן שלו . בכיוון ההפוך אגב מבדילים בין "אב" (parent) ל"אב קדמון" (ancestor).

בכל מקרה, כיוון שמדובר בעץ, זה מאוד פשוט - תתחיל מ-j ותבדוק מי האבא שלו (באמצעות המטריצה כמובן). תמשיך ותבדוק מי האבא של הצומת הזה, ומי האבא שלו וכן הלאה. אם תגיע ל-i - איזה יופי, יש מסלול (המסלול ההפוך מזה שהלכת בו). אם נתקעת (כלומר הגעת לשורש), אז אין מסלול.

אם זה היה סתם גרף מכוון ולא עץ, אז זה גם היה אפשרי באמעות פונקציית סריקה פשוטה (DFS או BFS).

[robicon]

הבעיה שאם מדובר בN ממש גדול ואם יש לצאצא יותר מאבא אחד...

רקורסיה יכולה לעבוד פה באופן טוב או שהזמן ריצה יהיה גדול מדי?

[שניצל]

לאף צומת בעץ לא יכול להיות יותר מאבא אחד, כי אז זה לא היה עץ. יכול להיות שזה סתם גרף כללי, ואז כמו שאמרתי צריך לעבוד אחרת (DFS). בכל מקרה הסיבוכיות תהיה לא יותר מ-(O(N^2. אם לכל צומת בעץ היה נתון מי האבא שלו (במקום מטריצה השכנויות) אז הסיבוכיות הייתה (O(N.

רקורסיה לא חוסכת זמן, זו פשוט דרך מימוש אחרת.

[robicon]

אוקיי...תודה.

[robicon]

יש לי עוד שאלה.

איך אני מקבל קלט מהמשתמש לתוך המטריצה אבל שלא יהיה כל פעם להכניס משתנה אחד אלה שיהיה הכל ביחד? למשל:

{{0,1,1,1,0},{0,0,1,1,0},{0,0,0,0,0}}

כרגע אני פשוט מבקש ממנו להכניס מספר ללחוץ אנטר ולהכניס עוד אחד וכו...

[שניצל]

תקרא את מחרוזת הקלט בשלמותה ואז תפרסר (parse) אותה בעצמך (באמצעות חיפוש תווים ו/או ביטויים רגולרים).

[robicon]

אין אופציה לעשות שהמערך שווה ל scanf ואז המשתמש ישר מכניס את הערכים?

[שניצל]

לא. scanf יודעת לקרוא רק מחרוזות ומשתנים פרימיטיביים (int,double וכד').

תזכור ש-C היא שפה שהחבילה הסטנדרטית שלה (דהיינו הפונקציות המובנות בתוך השפה) היא מאוד מינימליסטית. ב-++C לדוגמה יש לחבילה הסטנדרטית הרבה יותר כוח (סתם לדוגמה - אם אתה לא יודע מראש מה אורך המחרוזת המקסימלי שהמשתמש הולך להכניס, אז ב-C זה יחסית מסורבל לטפל בזה, אבל ב-++C יש פונקציה שעושה את כל העבודה בשבילך). בשפות יותר חדשות כמו #C ו-Java יש חבילה סטנדרטית מאוד רחבה שתאפשר לך לעשות את הדברים האלה הרבה יותר בקלות.

[robicon]

הבנתי...תודה

נראה לי שאני יעשה לולאה ואתן למשתמש למלא את המערכים עם scanf ככה גם אני יכול לשלוט בכמות משתנים שהוא מכניס

למרות שבמערכים ממש גדולים זה לא נוח.

תודה על ההסבר.