שאלה בגרפים

[lebron james2]

שאלה בגרפים

נתון גרף לא מכוון ולא ממושקל (G=(V,E, ושתיי קבוצות קדקדים S,T שמוכלות ב-V.
כתוב אלגוריתם יעיל המוצא את כל הקדקדים שנמצאים על מסלול פשוט כלשהו בין זוג קדקדים שהאחד מ-S והשני מ-T.

זו שאלה מתוך תרגיל בנושא של BFS,DFS,TOPOLOGIAL SORT and STRONGLY CONNECTED COMPONENTS.
ככה שאני מניח שצריך להתבסס על הדברים האלה.
מאחר והגרף כאן לא מכוון, אז נראה לי רכיבים קשירים היטב פחות רלוונטי כאן. רכיבים קשירים היטב מוגדרים עבור גרפים מכוונים.

אשמח לעזרה.

 

[lebron james2]

מישהו יכול בקשה לנסות לעזור???

 

[kמיר]

תשובה

יש לי רעיון שאולי יש יעיל ממנו.
אפשר ליצור גרף חדש new_G שנבנה בעזרת G.
ל- new_G נוסיף שני צמתים source_1 ו- source_2.
כמו כן נוסיף קשתות מ- source_1 לכל צומת ב- S וגם קשתות
מ- source_2 לכל צומת ב- T.
נריץ BFS מ- source_1 ונשמור בצד את הצמתים שהתגלו, נניח שקוראים לקבוצה הזו A. אותו דבר נעשה מ- source_2 ו נניח שהקבוצה שהתקבלה היא B.
קבוצת כל הקודקודים שנמצאים על מסלול כלשהוא בין S ל- T היא החיתוך של A ו- B.

 

[lebron james2]

פתרון מעניין. יפה! נראה טוב דווקא