רוטר - שאלה קצת מפגרת במבנה נתונים

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"שאלה קצת מפגרת במבנה נתונים"

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #21099	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 21099

jon snow

חבר מתאריך 18.7.13
655 הודעות, 1 פידבק, 1 נקודות

18:52 20.01.15

שאלה קצת מפגרת במבנה נתונים

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

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
כן וממליץ לך להתסתכל על האלגוריתמים של קרוסקל ופרים למציאת אחד כזה	Dark-Wish	20.01.15 22:33	1
אני מכיר את האגוריתמים	jon snow	21.01.15 11:51	2
אני לא חושב שזה מתאים	Dark-Wish	21.01.15 18:36	3

Dark-Wish
חבר מתאריך 25.5.05
12576 הודעות, דרג אמינות חבר זה

22:33 20.01.15

1. כן וממליץ לך להתסתכל על האלגוריתמים של קרוסקל ופרים למציאת אחד כזה
בתגובה להודעה מספר 0

שים לב שהעץ פורש מינימלי לא חייב להיות יחיד

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

jon snow

חבר מתאריך 18.7.13
655 הודעות, 1 פידבק, 1 נקודות

11:51 21.01.15

2. אני מכיר את האגוריתמים
בתגובה להודעה מספר 1

וזה שיש יותר מעץ פורש אחד זה מה שמקשה עליי בפתרון לבעיה.
אתה יכול להסתכל רגע?
http://srv1.jpg.co.il/10/54bf731d8d5bf.png

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dark-Wish
חבר מתאריך 25.5.05
12576 הודעות, דרג אמינות חבר זה

18:36 21.01.15

3. אני לא חושב שזה מתאים
בתגובה להודעה מספר 2

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד