30-03-2006, 20:12
|
 |
|
|
חבר מתאריך: 20.06.03
הודעות: 5,616
|
|
|
מבני נתונים בשפת C ממשים לרוב באמצעות
מבנים (struct).
אך לייצוג גרפים ישנן שתי שיטות עיקריות, אני אדגים את השיטות.
נתון הגרף הבא (לא מכוון):
1. מטריצת סמיכות
מטריצת סמיכות הינה מטריצת הקודקודים (vertex) של הגרף, כאשר תוכן המטריצה מייצג את הקשתות.
כלומר על מנת לייצג את הגרף הזה, נבנה מטריצה בה מספר שורות ועמודות כמספר הקודקודים.
ממבט על מטריצה זו - לדוגמה שורה A, אנו למדים שיש רק קשת מ-A ל-B (יש ערך 1 בתא A,B).
מאחר וזהו גרף לא מכוון - המטריצה סימטרית סביב האלכסון - אם הגרף היה מכוון, המטריצה היתה מאבדת את הסימטריות שלה.
2. רשימת סמיכויות
זהו למעשה מבנה הנתונים שתצטרך קרוב לוודאי עבור האלגורתמים שאתה מעוניין לממש.
מבנה זה הינו רשימה סדורה (מערך לדוגמה) של קודקודים, כשכל איבר הינו מצביע לרשימת הקודקודים אליו אליהם הוא מתחבר (רשימת קשתות).
הסיבוכיות בשימוש במבנה זה הינה נמוכה בהרבה מהסיבוכיות של השימוש במטריצת סמיכויות. עבור תאוריה נוספת בנושא תורת הגרפים, פנה לספרות, לgoogle או לאתר של ניר אדר שם תמצא חומר תיאורטי נהדר.
|
ראשי
צ'אט
) ) .
מצב כלאיים
