ייצוגים של גרפים

מבנה נתונים ואלגוריתמים

ייצוגים של צומת

בדרך כלל הצעד הראשון בייצוג של גרף הוא מיפוי של הקדקודים לרצף של מספרים שלמים. הרצף (0,|v-1|) הוא הנוח ביותר בתוכניות בשפת C - שפות אחרות הגמישות יותר, מאפשרות בחירה גדולה יותר. המיפוי יכול להתבצע בעזרת כל אחד ממבני החיפוש, לדוגמא: עץ בינארי, טבלת גיבוב וכו'.

מטריצת שכנויות

לאחר מיפוי הקדקודים, ייצוג אפשרי פשוט של גרף הוא בעזרת מטריצת שכנויות a. המטריצה מכילה ערכים בוליאניים והיא בגודל |v| x |v|. aіj מקבל ערך אמת אם קיימת צלע המחברת את i ו- j. אחרת aіj מקבל ערך שקר.

רשימות שכנויות

רשימת שכנויות היא רשימה של קדקודים המקושרים לקודקוד נתון. בייצוג של גרף בעזרת שימוש ברשימות כאלה, יש ליצור רשימה מקושרת כזו עבור כל קודקוד. הוספה של צלע לגרף תיצור שתי כניסות ברשימות השכנויות - אחת בכל קצה.

מעבר על גרף

מעבר Depth-First

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

struct t_graph {

int n_nodes;

graph_node *nodes;

int *visited;

adj_matrix am;

}

static int search_index = 0;

void search( graph g ) {

int k;

for(k=0;k<g->n_nodes;k++) g->visited[k] = FALSE;

search_index = 0;

for(k=0;k<g->n_nodes;k++) {

if ( !g->visited[k] ) visit( g, k );

}

}

פונקצית visit נקראת באופן רקורסיבי:

void visit( graph g, int k ) {

int j;

g->visited[k] = ++search_index;

for(j=0;j<g->n_nodes;j++) {

if ( adjacent( g->am, k, j ) ) {

if ( !g->visited[j] ) visit( g, j );

}

הליך זה בודק כל אחת מ- |v|² הכניסות של מטריצת השכנויות, כך שזמן הסיבוכיות שלו הוא O(|v|²).

בייצוג הגרף בעזרת שימוש ברשימות שכנויות, פונקצית visit משתנה מעט:

struct t_graph {

int n_nodes;

graph_node *nodes;

AdjListNode *adj_list;

int *visited;

adj_matrix am;

}

void search( graph g ) {

... /* As adjacency matrix version */

}

void visit( graph g, int k ) {

AdjListNode al_node;

g->visited[k] = ++search_index;

al_node = ListHead( g->adj_list[k] );

while( n != NULL ) {

j = ANodeIndex( ListItem( al_node ) );

if ( !g->visited[j] ) visit( g, j );

al_node = ListNext( al_node );

}

}

יש לשים לב לעובדה שהנחנו את קיומה של מחלקת List שבה המתודות: ListHead, ListItem, ListNext, וכן את קיומה של מחלקת AdjListNode שבה המתודה AnodeIndex.

זמן הסיבוכיות של מעבר מסוג זה יכול נראה בבירור - O(|V|+|E|), מאחר שמתבצע ביקור בכל קודקוד וכל צלע מבוקרת פעמיים.

מעבר Breadth-First

לצורך מעבר על גרף בשיטה זו, יש צורך להשתמש בתור FIFO:

static queue q;

void search( graph g ) {

q = ConsQueue( g->n_nodes );

for(k=0;k<g->n_nodes;k++) g->visited[k] = 0;

search_index = 0;

for(k=0;k<g->n_nodes;k++) {

if ( !g->visited[k] ) visit( g, k );

}

void visit( graph g, int k ) {

al_node al_node;

int j;

AddIntToQueue( q, k );

while( !Empty( q ) ) {

k = QueueHead( q );

g->visited[k] = ++search_index;

al_node = ListHead( g->adj_list[k] );

while( al_node != NULL ) {

j = ANodeIndex(al_node);

if ( !g->visited[j] ) {

AddIntToQueue( g, j );

g->visited[j] = -1; /* C hack, 0 = false! */

al_node = ListNext( al_node );

}

}

}

}

מושגים

מטריצת שכנויות

מבנה עבור ייצוג של גרף, אשר בו קיום או אי-קיום של צלע המקשרת בין שני קדקודים מסומן בכניסה מתאימה במטריצה.

רשימות שכנויות

מבנה עבור ייצוג של גרף, אשר בו הצלעות מאוחסנות כרשימות של קשרים בין קדקודים.

מעבר Depth-First

מעבר על גרף תוך ביקור כל הקדקודים המחוברים ישירות לקודקוד התחלתי.

מעבר Breadth-First

מעבר על גרף תוך ביקור כל הקדקודים המחוברים לקודקוד אשר מחובר לקודקוד ההתחלתי, לפני ביקור קודקוד שני

המחובר לקודקוד ההתחלתי.

המשך ל: אלגוריתם דיאקסטרה חזרה ל: תוכן עניינים