|
|
עמוד:283
בסוף הפעלת האלגוריתם , כל קדקודי הגרף צבועים בצבע שחור . 5 . 6 . 2 אלגוריתם למציאת רכיבים קשירים בגרף לא מכוון בעזרת סריקה לרוחב ( BFS ) בגרף הלא מכוון G האלגוריתם DFS ( G ) מוצא את רכיבי הקשירות , והאלגוריתם BFS ( G , a ) -1 מוצא את רכיב הקשירות שהרכיב a נמצא בו . אפשר לשכתב בקלות את האלגוריתם BFS ( G ) כך שנוכל למצוא את כל רכיבי הקשירות . בתהליך של סריקת צומתי הגרף בשיטת BFS נשתמש במערך הבוליאני , Used כך Used [ v ] -v !> מציין אם ביקרנו בקדקוד 11 או לא . בנוסף , נשתמש במשתנה count אשר מונה את מספר הרכיבים הקשירים . להלן האלגוריתם המבוקש : count Tiplp < r 0 . 1 : ^^^ ^^^^ V ^^^ . 2 2 . 1 אם ל- Usedfv ] ערך , FALSE אז בצע 1 2 . 1 . 1 קרא לשגרה BFS [ G ] כאשר קדקוד המקור הוא . v count < - count + 1 2 . 1 . 2 הערות . . 1 קל לראות שסיבוכיות זמן הריצה של האלגוריתם היא . 0 (| £ | + | V |) . 2 אם ברצוננו להדפיס את כל הקדקודיס שנמצאים באותו רכיב קשיר של , V נוכל לעשות זאת בצורה רקורסיבית , בעורת פרישת עץ בשיטת inorder או , preorder בזמן . O (| Vj )
|
|