wow1234 תפוז
New member
DFS
ראיתי את האלגוריתם של DFS. הבנתי שלכל קודקוד בגרף נשמרים : 1. ההורה 2. ה"time" שבו הגיעו אליו 3. הצבע שלו. האלגוריתם נראה כך : איתחול:
וכעת האלגוריתם עצמו:
רציתי לדעת במה כל אחד מהמשתנים שנשמרים לי לכל קודקוד עוזר לי למציאת תכונות של הגרף. לדוג' - איך "לשדרג" את האלגוריתם ע"מ שימצא אם יש לי מעגלים בגרף. וכעת השאלה העיקרית: נניח שנתון לי גרף לא מכוון שלכל קודקוד מקס' 3 שכנים. איך ניתן, בסיבוכיות הנמוכה ביותר, לדעת האם יש מעגל שגודלו לא מתחלק ב3, ואם כן להדפיס אותו. תודה רבה למדריכים ולעוזרים.
ראיתי את האלגוריתם של DFS. הבנתי שלכל קודקוד בגרף נשמרים : 1. ההורה 2. ה"time" שבו הגיעו אליו 3. הצבע שלו. האלגוריתם נראה כך : איתחול:
for all nodes u do { colour=white; p=NULL; } time = 0; for all nodes u do if colour == white then DFS(u);
וכעת האלגוריתם עצמו:
DFS(u): visit(u); time = time + 1; d = time; colour = grey; for all nodes v adjacent to u do { if colour[v] == white then { p[v] = u; DFS(u); } } time = time + 1; f = time; colour = black;
רציתי לדעת במה כל אחד מהמשתנים שנשמרים לי לכל קודקוד עוזר לי למציאת תכונות של הגרף. לדוג' - איך "לשדרג" את האלגוריתם ע"מ שימצא אם יש לי מעגלים בגרף. וכעת השאלה העיקרית: נניח שנתון לי גרף לא מכוון שלכל קודקוד מקס' 3 שכנים. איך ניתן, בסיבוכיות הנמוכה ביותר, לדעת האם יש מעגל שגודלו לא מתחלק ב3, ואם כן להדפיס אותו. תודה רבה למדריכים ולעוזרים.