DFS

בהינתם גרף, הסריקה $DFS=\text{ Depth First Search}$ עוברת על כל הקודקודים של הגרף באופן הבא: כל עוד יש קודקוד שלא ביקרנו בו, נבקר בו. כאשר מבקרים בקודקוד כלשהו, בודקים אם יש מישהו משכניו שטרם ביקרו בו- ואם כן מבקרים בו בקריאה ריקורסיבית.
בהינתן גרף מכוון $G=(V,E)$ אלגוריתם ה DFS סורק את כל הקודקודים.
בדומה לאלגוריתם ה BFS גם האלגוריתם DFS משייך במהלך ריצתו לכל קודקוד אחד משלושה צבעים $\{\text{black, white, gray}\}$ או בקיצור $b,w,g$
שמסמלים את מצב הקודקוד.

לבן - טרם ביקרנו בקודקוד
אפור - ביקרנו אך טרם סיימנו לטפל
שחור - ביקרנו וסיימנו לטפל

כמו כן , לכל קודקוד נשמור שלושה ערכים
$d(u)$ - זמן הגעה
$f(u)$ - זמן עזיבה
$\pi (u)$ - קודקוד קודם. אפשר להסתכל על זה כאבא של הקודקוד הראשון וככה נקבל אוסף עצים, מכונה גם ״יער העומק״. יער העומק מתאר את העצים שנוצרים כתוצאה מהקריאות הריקרוסביות שנפעיל על הסריקה, כלומר הסימונים של מי ילד של מי כתוצאה מהריקורסיה תניב לנו כעצם חלוקה של הגרף לאוסף של עצים, הלוא זה יער העומק.
נשים לב שיער העומק תלוי בריצה הספציפית של האלגוריתם $DFS$ , לגרף נתון יכול להיות כמה יערות עומק פר ריצה.

DFS(G)
	if u in V 
		color[u] = w
		parent[u] = null
		
	// t is some sort of timestamp	
	t=0
	for u in V
		if color[u] = w
			DFS-Visit(u)
	
	DFS-Visit(u)
		color[u] = g
		t = t+1
		d[u] = t
		for v in adj(u)
			if color[v] = w
				DFS-Visit(v)
				parent[v] = u
		color[u] = b
		t = t+1
		f[u] = t 		

באלגוריתם הזה אנחנו סורקים עבור קודקוד מסוים את העומק הכי נמוך שנוכל ״לרדת״ כלומר מייצרים יער עומק הנמוך ביותר לפני שנלך לשכנים האחרים.

זמן הריצה הוא $O(|V|+|E|)$

תכונות

משפט הסוגריים

בכל חיפוש לעומק על גרף $G=(V,E)$ (מכוון או לא מכוון)
עבור כל זוג קודקודים $u,v\in G$ מתקיים בידיוק אחד מהשלושה

1. $[d[u],f[u]]\cap [d[v],f[v]]=\mathrm{\varnothing }$
2. $[d[u],f[u]]\subseteq [d[v],f[v]]$
3. $[d[u],f[u]]\supseteq [d[v],f[v]]$
   ואם $u\ne v$ אז ההכלה בטוח לא שווה.

מסקנה : קודקוד $v$ הוא צאצא של $u$ ביער העומק אמ״מ מקרה 3 מתקיים.

משפט המסלול הלבן

$v\in V$ הוא צאצא של $u\in V$ ביער העומק אם ורק אם בזמן $d[u]-1$ קיים ב $G$ מסלול מ $u$ ל$v$ שכל קודקודים צבועים בלבן.
נוכיח את שתי הכיוונים
$\leftarrow$ אם $v$ צאצא של $u$ ביער עומק הרי קיים מסלול מ $v$ ל $u$ ביער ובפרט בגרף $G$. כל הקודקודים על גבי מסלול זה הם צאצאים של $u$ ולכן על פי משפט 1 לכל הקודקודים $x$ הללו מתקיים $d[u]<d[x]$ ולכן בזמן $d[u]-1$ כולם צבועים בלבן כולל $u$.

$\to$ נניח שבזמן $d[u]-1$ קיים מסלול מ $u$ ל $v$ שכל קודקודיו צבועים בלבן. נב״ש ש $v$ אינו צאצא של $u$ ביער העומק. נסתכל על המסלול הנ״ל וכעת, ניקח $w_1$ הקודקוד הכי קרוב ל$v$ על המסלול שהוא צאצא של $u$ ו $w_2$ הקודקוד הכי קרוב על העוקב במסלול שבהכרח אינו צאצא של $u$ (כמו באיור למעלה). כיוון ש $w_1$ צאצא של $u$ אזי

נשים לב שבזמן שביקרנו את $w_1$ בהכרח האלגוריתם בודק את הצבע של $w_2$. כמו כן, $w_2$ לבן כי הוא לא צאצא של $u$, אם הוא היה היינו מבקרים בו כבר בשלב בדיקת העומק על הקודקוד $u$. אבל $w_1$ צאצא של $u$ כלומר אנחנו עדיין בשלב הסריקת עומק של $u$ ולכן יתקיים

שלפי משפט הסוגריים זה נכון אמ״מ $w_2$ צאצא של $u$ ובפרט גם $v$ בסתירה .

מיון טופולוגי

הגדרה: גרף מכוון ללא מעגלים או $DAG=\text{Directed Acyclic Graph}$ הוא גרף מכוון שלא מכיל אף מעגל.
בהינתן גמ״ל נרצה סידור מיוחד של הקודקודים משמאל לימין שבו כל הקשתות הן בכיוון משמאל לימין. כלומר עבור גרף $G=(V,E)$ שהוא DAG , נגדיר שמיון טופולוגי הוא סידור

של הקודקודים ב $V$ כך שכל קשת $(v_i,v_j)\in E$ תקיים $i<j$ .
במילים יפות, זה אומר שנרצה שלאחר מיון נשים את כל הקודקודים לפי הסדר שקיבלנו בשורה וכל הקשתות יופנו לימין .

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

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

ניתן לראות ש קודקוד מספר 1 הוא שכן של 2 ו3 ולכן הוא יהיה לפניהם בסידור והם שכנים של 4 ולכן הם מופיעים לפניו וכן הלאה כלומר אם נסדר את הגרף במיון טופולוגי נקבל משהו כזה:

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

האלגוריתם

אם כן מיון טופולוגי של קודקודי גמ״ל $G=(V,E)$ ייראה כך

Topological-Sort(G):
	DFS(G)
	return sorted V by f[u] in decreasing order

זמן הריצה הוא $O(|V|+|E|)$. נוכיח נכונות, כל מה שצריך להוכיח זה שבסוף הריצה של הפונקצייה, לכל קשת $(v_i,v_j)\in E$ מתקיים $i<j$ .
ניקח קשת מהצורה הנ״ל ונרצה להוכיח ש $f[v_i]>f[v_j]$ באופן הזה אנחנו יודעים שאלגוריתם DFS עזב את $v_i$ לפני $v_j$ כלומר לאחר מיון $i<j$ .
נפריד לשני מקרים:
א) אם $d[v_i]<d[v_j]$ אז בזמן $d[v_i]-1$ יש מסלול לבן מ $v_i\to v_j$ הלוא היא הקשת המדוברת. שכן אנחנו יודעים בוודאות שלפני ששהגענו ל $v_i$ בוודאות לא הגענו גם ל $v_j$ . לפי משפט המסלול הלבן ביער העומק שיווצר כתוצאה מהסריקה $v_j$ הוא צאצא של $v_i$ כלומר

ב) אם $d[v_j]<d[v_i]$ אז לפי משפט הסוגריים יש שתי אפשרויות, או שהזמנים זרים ובגלל זה יתקיים אוטומטי

שזה בידיוק מה שרצינו.

או שיש הכלה ובגלל הנתון היא תהיה

כלומר ישנה הכלה לא שווה ולכן $v_i$ צאצא של $v_j$ ביער העומק אבל בגלל הקשת $(v_i,v_j)$ זה ייצור לנו מעגל בסתירה לכך שהגרף גמ״ל.

רכיבים קשירים היטב

בגרפים לא מכוונים הגדרנו רכיבי קשירות כקבוצות מקסימומיות כך שקיים מסלול בין כל זוג קודוקדים בקבוצה. בגרפים מכוונים המסלולים חייבים להיות מכוונים.
נגדיר רכיב קשיר היטב/ רכיב קשירות חזק $\text{S.C.C- Strongly Connected Component}$ בגרף מכוון $G=(V,E)$ כ קבוצה מקסימומית $C\subseteq V$ כך שלכל $u,v\in C$ מתקיים

כלומר , קיים מסלול ב $C$ משתי הכיוונים.

נגיד ש $G$ ייקרא קשיר היטב אמ״מ $G$ מכיל בידיוק רכיב קשיר היטב אחד.

הגדרה: נגדיר את גרף ה SCC על $G=(V,E)$ כ $G^{SCC}=(V^{SCC},E^{SCC})$ כאשר $V^{SCC}$ היא קבוצת הרכיבים הקשירים היטב של $G$. בנוסף עבור שני רכיבים קשירים היטב שונים $C_1,C_2\in V^{SCC}$ מתקיים

נראה אלגוריתם ליניארי למציאת רכיבי הקשירות החזקה
נתחיל מלחשוב על אלגוריתם הDFS. כאשר מריצים את אלגוריתם הDFS על גרף לא מכוון מקבלים יער, שבו העצים הם בדיוק רכיבי הקשירות של G. למה? כי מרגע שהפונקציה הראשית הביאה אותנו לקודקוד, אנו סורקים ע״פ משפט המסלול הלבן את כל מי שאיתו באותו רכיב. ומצד שני כמובן שלא ניתן להגיע מרכיב אחד לשני בלי לחזור ללואה בפונקציה הראשית.
מה יקרה אם נריץ את אלגוריתם ה־DFS על גרף מכוון? אנו כמובן עוברים לדבר על רכיבי קשירות חזקה. באופן דומה למצב בגרף לא מכוון ־ מרגע שהאלגוריתם מגיע לקודקוד כלשהו, הוא יסרוק את כל הרכיב הקשיר החזק שלו (ע״פ משפט המסלול הלבן ־ כל הקודקודים ברכיב הקשיר החזק יהיו בעץ), אולם ייתכן שיהיו בעץ גם קודקודים נוספים, כלומר כאלה שלא שייכים לאותו רכיב למשל בתמונה למטה, ניתן לראות שהעץ השמאלי הוא לא רכיב קשיר חזק היטב.

משפט : עבור גרף מכוון $G=(V,E)$ ויהי $C\subseteq V$ רכיב קשיר חזק ב $G$ . יתקיים שלאחר ריצת DFS על $G$ כל קודקודי $C$ נמצאים באותו יער עומק.

הוכחה:
יהי $v\in C$ הקודקוד הראשון שמגיעים אליו ב $C$ בזמן ריצת DFS . אם כן, בזמן $d[v]-1$ קיים מסלול לבן מ $v$ לכל קודקוד אחר $u\in C$ ברכיב, וממילא על פי משפט המסלול הלבן $u$ צאצא של $v$ ביער העומק, ובפרט נמצא באותו עץ, וממילא כל קודקודי $C$ נמצאים באותו עץ.

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

הגרף המשוחלף

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

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

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

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

לפי המשפט שטענו למעלה, הבעיה היחידה בפלט של DFS עלולה להיות שיהיה עץ שיכיל יותר מרכיב אחד. ננסה לנתח את האפשרות הזאת.
נסתכל על עץ $T$ כלשהו ביעד העומק, נסמן את שורשו ב $x\in V$ , רכיב הקשירות החזקה אליה הוא שייך יהיה $C$.

אנחנו יודעים ש $C\subseteq T$ אבל עלולים להיות רכיבים נוספים. נניח שיש רכיב נוסף ונסמנו $D$. אזי, בעץ יש מסלול כלשהו מקודקוד ב $C$ לקודקוד ב $D$ ואותו מסלול קיים גם ב $G^T$ באופן הפוך.
נוכיח בהמשך את הטענה שאם בגרף $G$ יש מסלול מ $C$ ל $D$ אז לא ייתכן שיהיה גם בכיוון ההפוך.
המטרה שלנו היא להבטיח ש $D$ ו $C$ לא יהיו ביחד ביער העומק. נעשה זאת על ידי כך שנבטיח שכאשר האלגוריתם סורק את קודקודי $C$ כל הקודקודים ב $D$ כבר יהיו בצבע שחור, כלומר כבר יהיו אחרי סיום סריקתם.

אלגוריתם למציאת SCC

כדי להבין איך נוכל להבטיח את ההבטחה הנ״ל, נחשוב על ריצת DFS הראשונה על הגרף $G$ . אנחנו יודעים שבגרף זה יש מסלול מקודקוד $D$ לקודקוד $C$ ואין מסלול מ $C$ ל $D$ . לכן, בריצת $DFS(G^T)$ נעבור על הקודקודים בסדר יורד של זמני הסיום של הקודקודים בהרצת $DFS(G)$ .
באופן הזה מובטח שבסריקת $DFS(G^T)$ נעבור קודם על הקודקודים ב $D$ , ולכן כאשר נסרוק את הקודקודים ב $C$ הרכיב $D$ יהיה כולו שחור ולא יוכל להצטרף לעץ.

SCC(G)
	DFS(G) \\this it only to calculate f[v] 
	calculate G_T
	run DFS(G_T) where V is sorted by f[v] in decreasing order
	every tree in the forset is one SCC 

נכונות

למה: יהי $C,D$ שני רכיבים קשירית היטב בגרף $G$ ויהיו $u,v\in C$ וגם $x,y\in D$ .
אם קיים מסלול $u\to x$ ב $G$ אז אין מסלול ב $G$ $v\to y$ .

הוכחה:
על פי הנתון קיים מסלול $u\to x$ . נניח בשלילה שקיים גם $v\to y$ . נרצה להראות שבמצב זה $C=D$
יהיו $w,w^{\prime }\in C\cup D$ שני קודקודים.
אם שניהם שייכים לאותו רכיב אז קיים מסלול בין שניהם משני הכיוונים ולכן $C=D$.
נניח בלי הגבלת הכלליות ש $w\in C{w}^{\prime }\in D$ . במצב זה על פי הנתונים

וגם

כלומר מצאנו שיש מסלול בינהם משני הכיוונים כלומר הם באותו רכיב קשיר היטב. כלומר קודקודי
$C\cup D$ מוכלים באותו רכיב קשיר היטב אבל אנחנו יודעים מההגדרה שרכיב קשיר היטב הוא קבוצה מקסימומית אז לא ייתכון ש $C,D$ הם רכיבי קשירות בפני עצמם הם חייבים להיות אותו רכיב הלוא הוא $C=D=C\cup D$ . כדרוש

הגדרה: יהי $G=(V,E)$ גרף מכוון עם ריצת DFS מסויימת, ותהי $U\subseteq V$ תת קבוצה של הקודקודים. נסמן :

למה:
עבור $C,D$ שתי רכיבים קשירים היטב בגרף $G$ ויהיו $v\in D,u\in C$ כך ש $(u,v)\in E$
אזי מתקיים $f(C)<f(D)$.
נחלק למקרים

א) $d(C)<d(D)$ : יהי $x\in C$ הקודקוד שמתגלה ראשו מקודקודי $C$ כלומר $d[x]=d(C)$ .
בזמן $d[x]-1$ כל הקודקודים של C ו D לבנים. בנוסף, יש מסלול מ $x$ לכל קודקוד ב $C$ ובפרט ל $u$ כלומר דרך הקשת הנתונה נוכל להגיע לכל קודקודי $D$ גם כן. כלומר כל הקודקודים ב $C$ ו $D$ יהיו צאצאים של $x$ ביער העומק. כלומר ממשפט הסוגריים

ובפרט עבור $\underset{y\in D}{max}(f[y])$ שזה בידיוק $f(D)$ ונשים לב ש $f(x)$ זה בידיוק $f(C)$

ב) אם $d(D)<d(C)$ עבור $x\in D$ הקודקוד שמתגלה ראשון מקודקודי $D$ כלומר $d[x]=d(D)$ ממשפט הסוגריים אנחנו יודעים ש $f(D)=f[x]$ .
נניח בשלילה ש $f(C)<f(D)$ אם ניקח $y\in C$ הקודקוד הראשון שמתגלה מקודקודי $C$ כלומר $d[y]=d(C)$ אז ממשפט הסוגריים נקבל ש $y$ צאצא של $x$ ביער העומק אבל זה לא ייתכן כי אנחנו יודעים ש $(u,v)$ היא קשת מחברת בין רכיבים קשירים היטב ולכן אין קשת $(v,u)$ כלומר לא ייתכן שסיימנו לסרוק את $C$ לפני שסיימנו לסרוק את $D$ , בהכרח $f(C)>f(D)$.

מסקנה מיידית היא שבגרף המשוחלף : $f(C)>f(D)$

משפט נכונות האלגוריתם:
כעת ניתן להוכיח שעבור גרף מכוון $G$ האלגוריתם SCC מחזיר את רכיבי הקשירות של הגרף.
נוכיח שכל עץ ביער העומק הוא רכיב קשיר היטב.
אנחנו כבר יודעים שכל רכיב קשיר מוכל בעץ. כעת , נניח בשלילה שיש עץ ביער העומק של ריצת ה DFS השנייה שמכיל לפחות שני רכיבי קשירות חזקים שונים.
ניקח את $x$ שורש העץ הזה, ונגדיר ש $C^{\prime }$ הוא רכיב הקשירות החזק שלו.
בעץ יש לפחות שני רכיבי קשירות כלומר קיימת קשת שמחברת בין הרכיבים ונסמן אותה $(u^{\prime },u)$ כאשר $u^{\prime }\in C^{\prime }$ ו $u\in C$ הרכיב קשירות השני.
האלגוריתם סורק את הקודקודים בסדר יורד לפי $f$ והקודקוד הראשון שנסרק הוא $x$ אחרת הוא לא היה השורש. כיוון שהוא מ $C^{\prime }$ הרי שמהלמות שלנו יתקיים

ומצד שני , מהמסקנה נקבל שבגרף המשוחלף $f(C)>f(C^{\prime })$ כי $(u^{\prime },u)\in E^T$, בסתירה. כלומר לא קיים עץ במכיל שני רכיבים קשירות חזקה שונים.