CoE KKU

Depth-first search เป็นลักษณะทั่วไปของ preorder traversal เริ่มต้นด้วยการประมวลผลที่ vertex v ใด ๆ แล้วจากนั้นจะท่องไปในทุก vertices ที่เป็น adjacent กับ v ในแบบ recursive

ถ้าใช้การเดินท่องไปแบบที่กล่าวนี้กับทรีเราก็จะต้องใช้เวลาเป็น $O(|E|)$ เนื่องจากว่า $|E| = \Theta(|V|)$ และถ้าการท่องไปนี้กระทำกับกราฟเราจะต้องระมัดระวังไม่ให้เกิด cycles ขึ้น โดยเมื่อเราเข้าถึง vertex v ใด ๆ เราจะทำเครื่องหมายไว้ แล้วเรียกใช้ depth-first search แบบ recursive กระทำต่อ adjacent vertices ทั้งหมดที่ยังไม่มีเครื่องหมาย โดยเราจะถือว่าถ้าเป็น undirected graphs แล้วทุก ๆ edge (v, w) หนึ่งจะปรากฏอยู่ใน adjacency lists 2 ครั้ง คือ (v, w) และ (w, v) รูปที่ 9.57 แสดง depth-first search (โดยยังไม่ทำงานอื่น) ฟิลด์ visited ของแต่ละ vertex จะได้รับการกำหนดค่าเริ่มต้นเป็น false ด้วยการเรียกใช้โปรซิเจอร์ในแบบ recursive เฉพาะเมื่อมันเป็นโนดที่ยังไม่ได้รับการเข้าถึง (visited) เท่านั้นทำให้ประกันได้ว่าจะไม่เกิดการวนรอบไม่รู้จบ

void dfs ( Vertex v )
{
    v.visited = true;
    for each w adjacent to v
        if  ( !w.visited )
	       dfs( w );
}

รูปที่ 9.57 Template ของ Depth-first search

ถ้ากราฟเป็นแบบ undirected และไม่เป็น connected หรือถ้าเป็นแบบ directed และไม่เป็นแบบ strongly connected วิธีการดังกล่าวข้างบนอาจล้มเหลวในการเข้าถึงโนดบางโนด เราก็จะต้องค้นหาโนดที่ยังไม่มีเครื่องหมายแล้วใช้การทำงาน depth-first traversal กับมันต่อไป และจะทำเช่นนี้ไปจนกว่าจะไม่มีโนดที่ไม่มีเครื่องหมาย เนื่องจากวิธีการนี้จะประกันได้ว่าจะมีการเข้าถึงแต่ละ edge เพียงครั้งเดียว ดังนั้นเวลาที่ใช้ในการ traversal คือ $O(|E| + |V|)$ เมื่อใช้ adjacency lists

กราฟชนิด undirected graph เป็นกราฟแบบ connected ถ้าหากว่าการทำ depth-first search โดยเริ่มจากโนดใดโนดหนึ่งแล้วสามารถเข้าถึงโนดได้ทุกโนด อัลกอริทึมที่จะกล่าวถึงต่อไปจะถือว่ากราฟเป็นแบบ connected อยู่แล้วและถ้ากราฟเป็นแบบ unconnected เราก็สามารถหาส่วนที่เป็น connected และใช้อัลกอริทึมของเรากับแต่ละส่วนได้

ตัวอย่าง depth-first search ของกราฟรูปที่ 9.58 โดยเริ่มที่ vertex A ให้ทำเครื่องหมายที่ A เมื่อได้เข้าถึงมันแล้วและเรียกใช้ dfs(B) ในแบบ recursive ซึ่งจะทำเครื่องหมายที่ B และเรียกใช้ dfs(C) ในแบบ recursive ทำเครื่องหมายที่ C และเรียกใช้ dfs(D) แบบ recursive ซึ่ง dfs(D) จะมองเห็น A และ B แต่เนื่องจากทั้งสองนี้ถูกทำเครื่องหมายการเข้าถึงเอาไว้แล้วจึงไม่เรียกฟังก์ชัน recursive อีกต่อไปและจะกลับไปยัง dfs(C) ซึ่ง dfs(C) มองเห็น B ก็จะถูกละเลยไปเช่นกัน แต่จะมองเห็น E และเรียกใช้ dfs(E) และทำเครื่องหมายที่ E ละเลย A และ C จากนั้นกลับคืนมาที่ dfs(C) จาก dfs(C) กลับมาที่ dfs(B) และที่ dfs(B) ละเลย A และ D จากที่ dfs(B) กลับมาที่ dfs(A) และที่ dfs(A) ละเลย D และ E และ return กลับ

เราสามารถเขียนรูปแสดงขั้นตอนการทำงานการเดินท่องที่กล่าวมาข้างบนนี้ได้ด้วยทรีที่เรียกว่า depth-first spanning tree ได้ดังนี้ Vertex แรกที่เข้าถึง คือ A ให้เป็นรากของทรี โดยแต่ละ edge (v, w) ในกราฟจะแสดงให้ปรากฏในทรี ในขณะที่ประมวลผล edge (v, w) นั้นถ้าพบว่า w ยังคงไม่ถูกทำเครื่องหมาย (unmarked) หรือขณะประมวลผล edge (w, v) พบว่า v ยังไม่ถูกทำเครื่องหมาย เราก็จะกำหนดให้มีการสร้าง edge ขึ้นในทรีเรียกว่า tree edge ซึ่งแสดงด้วยเส้นทึบปกติเชื่อมต่อระหว่างโนด ถ้าขณะประมวลผล (v, w) พบว่า w ได้รับการทำเครื่องหมายแล้ว (marked) และขณะประมวลผล (w, v) พบว่า v ได้รับการทำเครื่องหมายแล้ว เราก็จะเขียนเส้นเชื่อมต่อระหว่าโนดให้เป็นเส้นประ และเรียกว่า back edge เพื่อระบุว่า “edge” นี้ไม่ได้เป็นส่วนหนึ่งของ tree รูปที่ 9.59 เป็น depth-first search tree ของกราฟในรูปที่ 9.58

รูปที่ 9.58 Undirected graph	รูปที่ 9.59 depth-first search tree ของกราฟในรูปที่ 9.60

Depth-first search tree เป็นรูปแบบจำลองการเดินท่องในกราฟ การกำหนดหมายเลขตามลำดับของ preorder ของ vertex ในทรีที่ใช้เฉพาะ edge ที่เป็น tree edges เท่านั้นจะเป็นหมายเลขที่บอกถึงลำดับที่ vertex นั้นได้รับการทำเครื่องหมายเข้าถึงมัน ถ้ากรณีที่กราฟไม่เป็นกราฟแบบ connected แล้วการเดินท่อง (หรือประมวลผล) ให้ครบทุกโนดนั้นก็จะต้องการการเรียกใช้ dfs หลาย ๆ ครั้งและแต่ละครั้งที่เรียกใช้ dfs นั้นก็จะได้ Depth-first search tree ขึ้นมา 1 ทรี กลุ่มทรีที่ได้ทั้งหมดเรียกว่า depth-first spanning forest

กราฟที่เป็น connected undirected graph เรียกว่าเป็นกราฟแบบ biconnected ถ้ากราฟนั้นไม่มี vertices ที่เมื่อย้าย (หรือลบมันออกไป) มันออกไปจากกราฟนั้น ๆ แล้วทำให้ได้กราฟที่เหลือเป็นกราฟแบบ disconnects กราฟในรูปข้างบนที่ผ่านมานั้นเป็นกราฟแบบ biconnected ระบบขนส่งมวลชนเป็นระบบแบบ biconnected ถ้าผู้สัญจรสามารถที่จะเลือกเดินทางอื่นไปยังจุดหมายที่ต้องการได้เสมอถึงแม้ว่าเส้นทางที่ต้องเลือกไว้แต่แรกมีปัญหา

ถ้าหากว่ากราฟไม่เป็นแบบ biconnected แล้ว vertices ที่เมื่อย้ายมันออกไปแล้วทำให้กราฟเป็น disconnect เรียกว่าข้อต่อของกราฟ (articulation points) โนดดังกล่าวนี้มีความสำคัญมากในงานประยุกต์บางอย่าง กราฟในรูปที่ 9.60 ไม่เป็น biconnected และมีโนด C และ D เป็น articulation points และการย้าย C ออกจากกราฟจะทำให้โนด G ถูกตัดออกจากกราฟ และการย้ายโนด D ออกทำให้โนด E และ F ถูกตัดออกจากกราฟ

รูปที่ 9.60 กราฟที่มีข้อต่อคือโนด C และ D	รูปที่ 9.61 รูป depth-first search tree ของกราฟรูปที่ 9.60

การทำ Depth-first search กับกราฟจะสามารถค้นหา articulation points ทั้งหมดใน connected graph โดยใช้เวลาเป็น linear-time ได้ดังนี้ ให้เริ่มทำ depth-first search เริ่มต้นที่ vertex ใด ๆ และให้หมายเลขโนดเมื่อเข้าถึงตามลำดับ preorder number หมายเลข preorder ที่ให้กับแต่ละ vertex v นี้เราจะเรียกว่า Num(v) จากนั้นสำหรับแต่ละ vertex v ใน depth-first search spanning tree ให้หา vertex ที่มีหมายเลขต่ำสุดที่สามารถไปถึงได้จาก v โดยการเดินท่องด้วยการใช้ tree edge หรืออาจจะไม่ได้ใช้ tree edge เลยและใช้หนึ่ง back edge ถ้ามี (ตามลำดับของ edge ที่ปรากฏ) และเรียกค่าของ vertex ที่ได้นี้ว่า Low(v) รูป depth-first search tree ในรูปที่ 9.61 แสดงหมายเลข preorder number และตามด้วยหมายเลขต่ำสุดของ vertex ที่ไปถึงได้ตามกฎที่กล่าวข้างบนนี้

หมายเลข vertex ต่ำสุดที่สามารถเดินท่องไปถึงได้จากโนด A, B, และ C คือ vertex หมายเลข 1 (A) เนื่องจากทั้งหมดนั้นใช้ 3 tree edges ไปยัง D และอีกหนึ่ง back edge เพื่อกลับไปยัง A เราสามารถคำนวณหาค่า low ได้ด้วยการใช้ postorder traversal ใน depth-first spanning tree จากนิยามของค่าของ Low(v) เราจะพบว่าค่าที่เป็นได้ของ Low(v) คือค่าใดค่าหนึ่งใน 3 ข้อต่อไปนี้ คือ

1. Num(v)
2. ค่า Num(w) ที่น้อยที่สุดในกลุ่ม back edges (v, w)
3. ค่า Low(w) ที่น้อยที่สุดใน tree edges (v, w)

ข้อ 1. เกิดเมื่อไม่มีการใช้ edges เช่นทรีดังรูปข้างล่างนี้	ข้อ 2. เกิดเมื่อไม่มีการใช้ tree edges และมีหนึ่ง back edge ดังรูปข้างล่างนี้	ข้อ 3. เกิดเมื่อมีการใช้ tree edges และอาจมีหนึ่ง back edge ดังรูปข้างล่าง

เนื่องจากว่าเราจะต้องหาค่า low ของโนดลูกทั้งหมดของ v ให้ได้เสียก่อนที่เราจะสามารถหาค่า Low(v) ได้ นั่นคือเป็น postorder traversal กล่าวสำหรับ edge (v, w) ใด ๆ แล้วเราสามารถจะบอกได้ว่ามันเป็น tree edge หรือ back edge ได้ด้วยการตรวจดูค่า Num(v) และ Num(w) ดังนั้นไม่ยากที่จะคำนวณค่า Low(v) กล่าวคือเพียงแต่ scan ไปตาม adjacency list ของ v โดยใช้กฎดังกล่าวข้างบนและบันทึกค่าที่น้อยที่สุด การคำนวณทั้งหมดใช้เวลา $O(|E| +|V|)$ หน่วย

สิ่งที่เหลืออยู่คือ การใช้สารสนเทศที่ได้มาแล้วนั้นเพื่อการหา articulation points ของกราฟ กล่าวคือ รากของทรีเป็น articulation point ถ้าหากว่ามันมีโนดลูกมากกว่าหนึ่งโนด ทั้งนี้เพราะว่าการย้ายโนดรากจะทำให้ทรีย่อยของรากแยกออกจากกันคือมันเป็น disconnects ส่วน vertex v อื่น ๆ ที่เป็น articulation point ถ้าหากว่าโนด v มีโนดลูก w ใด ๆ ที่มี Low(w)≥ Num(v) ซึ่งจะเห็นว่าโนดรากมีคุณสมบัติที่สอดคล้องกับข้อนี้ด้วยเสมอ ดังนั้นจึงต้องใช้การตรวจสอบพิเศษด้วย

ในรูปที่ 9.61 โนด D มีโนด E เป็นโนดลูกและ Low(E) ≥ Num(D) เนื่องจากทั้ง 2 มีค่า 4 ดังนั้นมีเพียงหนทางเดียวที่จากโนด E จะสามารถกลับไปถึงโนดใด ๆ ที่อยู่เหนือโนด D ได้ก็เพียงผ่านทางโนด D เท่านั้น ในทำนองเดียวกัน C ก็เป็นโนดข้อต่อ เนื่องจาก Low(G) ≥ Num(C) รูปที่ 9.62 เป็นอีกตัวอย่างของทรีของกราฟเดิมที่เริ่มต้น depth-first search ที่โนด C

pseudocode สำหรับอัลกอริทึมแสดงไว้ในรูปที่ 9.63 ถึงรูปที่ 9.65 โดยกำหนดให้ Vertex ประกอบด้วยข้อมูลต่าง ๆ คือ ค่า visited (กำหนดให้ค่าเริ่มต้นเป็น false), num, low, และ parent เราจะทำบันทึกค่าตัวแปรของคลาส Graph คือ counter, โดยกำหนดค่าเริ่มต้นเป็น 1 เพื่อใช้เป็นตัวกำหนดค่า preorder traversal numbers ซึ่งก็คือค่า num

ดังที่กล่าวมาแล้วว่าเราสามารถคำนวณ Num ได้ด้วยการใช้ preorder traversal และใช้ postorder traversal เพื่อคำนวณค่า Low และใช้การ traverse อีกครั้งหนึ่งเพื่อหา articulation point

คำสั่งในรูปที่ 9.63 เป็นการทำงานการเดินท่องในทรีครั้งแรก การทำงานรอบที่สองและสามซึ่งเป็น postorder traversals ทำได้ด้วยโปรแกรมในรูปที่ 9.64 โดยบรรทัดที่ 8 ใช้เพื่อจัดการกรณีพิเศษ คือ ถ้า w เป็น adjacent ของ v แล้วการทำ recursive call กับ w จะพบว่า v เป็น adjacent กับ w แต่นี่ไม่ใช่ back edge แต่เป็น edge ที่ผ่านการพิจารณาแล้วและต้องละเลย นอกนั้นก็จะทำการคำนวณค่าต่ำสุดของ low และรายการค่า num ต่อไป รูปที่ 9.65 เป็นฟังก์ชัน findArt ซึ่งรวมฟังก์ชัน assignNum และ assignLow เข้าด้วยกัน

/* assign num and compute parents */
	void  assignNum( Vertex v )
	{
	    vertex w;
/*1*/   v.num = counter++;
/*2*/   v.visited = true;
/*3*/   for each w adjacent to v
/*4*/      if ( !w.visited )
	       {
/*5*/           w.parent = v;
/*6*/           assignNum( w );
	       }
	}

รูปที่ 9.63 Pseudocode ฟังก์ชันเพื่อกำหนดค่า Num ของ vertices

void assignLow( Vertex v )
{	    vertex w;
/*1*/   v.low = v.num;             	/* Rule 1 */
/*2*/   for each w adjacent to v
	    {
/*3*/       if  ( w.num > v.num )   	/* forward edge */
	        {
/*4*/           assignLow( w );
/*5*/           if  ( w.low >= v.num )
/*6*/               System.out.println ( v + " is an articulation point" );
/*7*/            v.low = min( v.low, w.low ); 		/* Rule 3 */
	        }  else
/*8*/             if  ( v.parent != w )      /* back edge */
/*9*/                 v.low = min( v.low, w.num ); 		/* Rule 2 */
	    }
}

รูปที่ 9.64 Pseudocode เพื่อคำนวณค่า low และทดสอบการเป็น articulation points (โดยไม่มีการทดสอบราก)

void findArt ( Vertex v )
{	    vertex w;
/*1*/   v.visited = true;
/*2*/   v.low = v.num = counter++; 	/* Rule 1 */
/*3*/   for each w adjacent to v
	    {
/*4*/       if ( !w.visited ) 	/* forward edge */
	        {
/*5*/           w.parent = v;
/*6*/           findArt( w );
/*7*/           if  ( w.low >= v.num )
/*8*/              System.out.println ( v + " is an articulation point" );
/*9*/           v.low = min( v.low, w.low ); 	/* Rule $ */
	        }  else
/*10*/            if  ( v.parent != w ) 			/* back edge */
/*11*/                 v.low = min( v.low, w.num ); 	/* Rule 2 */
	    }
}

รูปที่ 9.65 ทดสอบ articulation points ใน depth-first search (ไม่รวมราก) (pseudocode)

พิจารณารูปภาพ 3 รูปที่แสดงในรูปที่ 9.66 ปัญหาที่นิยมเล่นกันคือ ให้ใช้ดินสอสร้างรูปเหล่านี้ใหม่โดยลากเส้นแต่ละเส้นเพียงครั้งเดียวและต้องไม่ยกดินสอขึ้นขณะเขียนรูป ปัญหาที่อาจจะเพิ่มเติมขึ้นได้อีกโดยการกำหนดให้จุดเริ่มและกลับจบการเขียนที่จุดเริ่มต้น น่าแปลกที่เราสามารถแก้ปัญหานี้ได้ง่าย ๆ

รูปที่ 9.66 รูปวาด 3 รูป	รูปที่ 9.67 ปรับเปลี่ยนรูปวาดรูปที่ 9.66

รูปภาพแรกสามารถเขียนได้เมื่อเริ่มต้นที่มุมซ้ายหรือมุมขวาล่างเท่านั้นแต่จะไม่สามารถจบที่จุดเดียวกับจุดเริ่มต้นได้ ส่วนรูปภาพที่ 2 สามารถเขียนโดยให้มาจบที่จุดเดียวกับจุดเริ่มต้น แต่ภาพที่ 3 ไม่สามารถเขียนได้ตามเงื่อนไขการเขียนที่กล่าวมาแล้วข้างบน

เราสามารถเปลี่ยนปัญหาการเขียนรูปเหล่านี้ให้เป็นปัญหาของทฤษฎีกราฟได้โดยกำหนดให้จุดตัดของเส้นเป็น vertex ส่วน edges ก็เป็นเส้นเชื่อมต่อระหว่างจุดตัดตามปกติ ดังรูปที่ 9.67

หลังการสร้างกราฟเพื่อจำลองรูปแล้ว จากนั้นเราต้องหาเส้นทางในกราฟที่เข้าถึงแต่ละ edge เพียงครั้งเดียว หรือถ้าต้องการแก้ปัญหาที่ท้าทายมากขึ้นคือการหา cycle ที่เข้าถึงทุก edge เพียงครั้งเดียว (เริ่มและจบที่ vertex เดียวกัน) Euler แก้ปัญหาดังกล่าวนั้นได้ในปี 1736 ปัญหานี้เรียกว่า Euler path (หรือ Euler tour) หรือ Euler circuit problem แล้วแต่ตัวปัญหา ปัญหา Euler path และ Euler circuit แตกต่างกันเล็กน้อยแต่มีวิธีการแก้ปัญหาโดยพื้นฐานแล้วเหมือน ๆ กัน ดังนั้นในที่นี้จะกล่าวถึง Euler circuit

จะเห็นว่าการจะแก้ปัญหา Euler circuit ซึ่ง vertex เริ่มต้นและ vertex ที่จบเป็นจุดเดียวกันได้นั้นกราฟจะต้องเป็นแบบ connected และแต่ละ vertex จะต้องมีจำนวน edge เป็นเลขคู่ (vertex มีดีกรีเป็นคู่) ทั้งนี้เนื่องจากเมื่อเดินทางเข้าสู่ vertex ใดแล้วต้องเดินทางออกจาก vertex นั้น ถ้าหากว่ามี vertex v ใดที่มีดีกรีเป็นคี่แล้วเมื่อถึงจุดที่เหลือ edge เพียงเส้นเดียวที่ต้องใช้เดินทางเข้า vertex v นั้นแล้วก็จะไม่สามารถออกจาก vertex v นั้นได้ กล่าวสำหรับแก้ปัญหา Euler path แล้วการจะแก้ปัญหา Euler path ได้กราฟจะต้องมีสอง vertices ที่มีจำนวน edge เป็นเลขคี่และต้องเริ่มต้นการเขียนที่ vertex ที่มี edge เป็นคี่ตัวหนึ่งแล้วต้องจบที่ vertex ที่มี edge เป็นคี่อีก vertex หนึ่ง และถ้าหากกราฟมี vertices มากกว่าสองตัวที่มี edge เป็นเลขคี่ก็จะแก้ปัญหา Euler path ไม่ได้

จากที่ได้กล่าวมาข้างบนนี้เป็นการแสดงให้เห็นถึงเงื่อนไขที่จำเป็นของการมีอยู่ของ Euler circuit นั่นคือ กราฟแบบ connected ใด ๆ ก็ตามที่ vertices ทั้งหมดของมันมี edge เป็นจำนวนคู่ แสดงว่ากราฟนั้นต้องมี Euler circuit และสามารถหา circuit นั้นได้ด้วยเวลาเป็น linear time

โดยใช้อัลกอริทึมพื้นฐานคือทำ depth-first search ปัญหาใหญ่ของอัลกอริทึมที่เราใช้คือเราอาจจะเดินท่องไปในกราฟเพียงบางส่วนแล้วมีการจบการเดินท่องที่จุดเริ่มต้นก่อนเวลาอันควร และถ้าหากว่า edges ทั้งหมดของ vertex เริ่มต้นนั้นถูกใช้ไปทั้งหมดแล้วก็หมายความว่าต้องมีส่วนอื่นของกราฟที่ยังไม่ได้เดินท่องไป กรณีนี้เราสามารถแก้ได้ด้วยการค้าหา vertex แรกในเส้นทางที่เดินท่องไปแล้วนี้ที่ยังมี edge ที่ยังไม่ได้ใช้ เมื่อพบ vertex ดังกล่าวนี้แล้วให้ทำ depth-first search ใหม่อีกโดยเริ่มต้นที่ vertex นั้นก็จะได้ circuit ใหม่จากการเดินท่องนี้ซึ่งสามารถแทรกเข้าในระหว่าง circuit ที่ได้ก่อนหน้า และจะทำเช่นเดิมนี้ไปเรื่อย ๆ จนกว่าจะใช้ (หรือเดินท่องไป) ครบทุก edges

พิจารณากราฟรูปที่ 9.68 ซึ่งเป็นกราฟที่มี Euler circuit สมมติถ้าเริ่มต้นที่ vertex 5 และ traverse ไปตามวงจร 5, 4, 10, 5 ซึ่งทำให้ต้องหยุดการเดินท่อง และมีสภาวะของกราฟดังรูปที่ 9.69 โดยที่ edges ที่ใช้งานแล้วก็จะถูกเอาออกจากกราฟ

จากนั้นเริ่มใหม่ที่ vertex 4 และมี depth-first search เป็น 4, 1, 3, 7, 4, 11, 10, 7, 9, 3, 4 และถ้าเราแทรกวงจรเส้นทางนี้เข้าไปในเส้นทางของวงจรก่อนหน้าคือ 5, 4, 10, 5 ก็จะได้วงจรเป็น 5, 4, 1, 3, 7, 4, 11, 10, 7, 9, 3, 4, 10, 5 รูปที่ 9.70 แสดงสถานะ การเดินท่องที่ได้และจากรูปนี้จะเห็นว่า vertices ทั้งหมดมีดีกรีเป็นคู่นั่นหมายความว่าเราสามารถหา cycle เพิ่มเติมได้เสมอ กราฟที่เหลืออาจจะไม่เป็น connected graph แต่ก็ไม่ใช้เรื่องสำคัญ

vertex ถัดไปตามเส้นทางที่ยังไม่ได้เดินท่องไปคือ vertex 3 เส้นทาง circuit ที่เป็นไปไปได้ทางหนึ่งคือ 3, 2, 8, 9, 6, 3 และหลังจากแทรก circuit นี้เข้าใน circuit เดิมจะได้ 5, 4, 1, 3, 2, 8, 9, 6, 3, 7, 4, 11, 10, 7, 9, 3, 4, 10, 5 กราฟที่เหลือหลังการทำงานนี้แสดงในรูปที่ 9.71 vertex ที่เลือกบนเส้นทางที่เหลือที่ยังไม่ได้เดินท่องไปนี้คือ 9 และพบ circuit 9, 12, 10, 9 และเมื่อเพิ่ม circuit นี้เข้าในเส้นทางที่มีอยู่แล้วจะได้ circuit 5, 4, 1, 3, 2, 8, 9, 12, 10, 9, 6, 3, 7, 4, 11, 10, 7, 9, 3, 4, 10, 5 และเนื่องจากได้เดินท่องไปครบทุก edges ในกราฟแล้วก็เป็นอันเสร็จสิ้นการทำงานของอัลกอริทึม

เพื่อให้อัลกอริทึมมีประสิทธิภาพเราจะต้องใช้โครงสร้างข้อมูลที่เหมาะสม เพื่อให้การแทรก circuit ลงในเส้นทางเดิมทำได้ง่ายขึ้น เราอาจจะใช้การเก็บข้อมูลของเส้นทางเอาไว้ในโครงสร้าง linked list และเพื่อหลีกเลี่ยงการต้อง scan ใน adjacency lists ซ้ำ ๆ หลายครั้ง สำหรับแต่ละ adjacency list เราจึงต้องเก็บรายการของ edge ตัวสุดท้ายที่ได้ scan แล้ว เมื่อได้ทำการแทรกเส้นทางแล้ว เราจะทำการหา vertex ใหม่ที่จะเป็น vertex เริ่มต้นของวงจรใหม่ด้วย depth-first search ก็เริ่มต้นจากจุดแทรกที่ผ่านมานี้ การทำเช่นนี้จะประกันได้ว่าการทำงานในขั้นตอนของการค้นหา vertex รวมทั้งหมดนั้นใช้ $O(|E|)$ และด้วยการใช้โครงสร้างข้อมูลที่เหมาะสม running time ของอัลกอริทึม คือ $O(|E| + |V|)$

ปัญหาที่มีลักษณะเดียวกับที่กล่าวมาคือการหาเส้นทาง simple path ที่รวมทุก vertex ของกราฟ ปัญหานี้รู้จักกันในชื่อ Hamiltonion cycle problem (จะไม่กล่าวถึงในบทเรียนนี้)

การท่องไปใน directed graphs ก็สามารถทำได้ด้วยเวลาเป็น linear time โดยการใช้ depth-first search เช่นเดียวกับใน undirected graphs ดังนี้ ถ้าหากกราฟดังกล่าวไม่เป็น strongly connected แล้วการเริ่มการค้นหาด้วย depth-first ที่โนดใด ๆ จะไม่สามารถท่องไปในทุก ๆ โนดได้ ในกรณีเช่นนี้ เราจะทำ depth-first searches ซ้ำ ๆ โดยเริ่มที่โนดที่เป็น unmarked node ใหม่จนกระทั่งท่องไปครบทุกโนด ดังเช่นตัวอย่างกราฟแบบ directed ในรูปที่ 9.72

เราเริ่มการทำ depth-first search ที่ vertex B (ที่ vertex อื่น ๆ ก็ได้เช่นเดียวกัน) ซึ่งทำให้เดินท่องไปผ่าน vertices B, C, A, D, E, และ F จากนั้นก็เริ่มใหม่ที่ vertex ที่ยังไม่ได้เดินท่องผ่านไป ในที่นี้เลือกที่จะเริ่มใหม่ที่ H ซึ่งจะท่องผ่านไปที่ I และ J สุดท้ายเริ่มใหม่ที่ G ซึ่งเป็น vertex สุดท้ายที่จะท่องผ่านไป และจะได้ depth-first search tree ดังรูปที่ 9.73

ลูกศรที่เป็นเส้นประที่ปรากฏใน depth-first spanning forest เป็น edges (v, w) ที่โนด w ได้รับการทำเครื่องหมายที่แสดงว่ามันผ่านการเดินท่องมาแล้วก่อนหน้าที่จะเดินท่องผ่านในขณะนั้น ๆ ในกราฟที่เป็น undirected graph ลูกศรดังกล่าวนี้ก็จะเป็น back edges ได้เท่านั้น แต่ในกรณีที่กำลังกล่าวถึงนี้ ลูกศรนี้อาจเป็นของ edges ชนิดใดชนิดหนึ่งใน 3 ชนิดที่ไม่ได้เป็นเส้นทางที่จะนำไปสู่ vertices ใหม่ ชนิดแรกคือ back edges ดังเช่น (A, B) และ (I, H) ชนิดถัดมาคือ forward edges ดังเช่น (C, D) และ (C, E) ที่แสดงเส้นทางจากโนดของ tree ไปยังโนดที่ตามหลังมันมา และชนิดสุดท้ายคือ cross edges ดังเช่น (F, C) และ (G, F) ซึ่งเส้นเชื่อมต่อโนดของทรี 2 ทรีที่ไม่เกี่ยวข้องกันโดยตรง

ปกติแล้วการเขียนรูป depth-first search forest จะเพิ่มขนาดขึ้นจากด้านซ้ายมือไปขวามือ และ cross edges มักจะเขียนจากด้านขวามือมาทางด้านซ้ายมือ

บางอัลกอริทึมที่จำเป็นต้องใช้วิธี depth-first search อาจจำเป็นต้องสามารถจำแนก edges ทั้ง 3 ชนิดที่ไม่ใช่ tree edges ให้ได้ (nontree edges) ซึ่งก็สามารถทำได้ในระหว่างการทำงานของ depth-first search นั่นเอง (ลองคิดดู) ประโยชน์อย่างหนึ่งของ depth-first search คือสามารถใช้มันเพื่อทดสอบว่า directed graph นั้นเป็น acyclic หรือไม่

กฎก็คือ directed graph นั้นเป็นกราฟแบบ acyclic ก็ต่อเมื่อมันไม่มี back edges (กราฟในรูปข้างบนมี back edges ดังนั้นมันจึงไม่เป็นกราฟแบบ acyclic) ยังคงจำได้ว่าเราสามารถใช้ topological sort เพื่อการนี้ได้ทดสอบว่ากราฟเป็น acyclic หรือไม่ได้เช่นกัน การทำ topological sorting อีกทางหนึ่งคือ กำหนดค่า topological numbers ให้แก่ vertices เป็น N, N – 1, . . . ,1 ด้วยการทำ postorder traversal ใน depth-first spanning forest ลำดับค่านี้จะเป็นเช่นเดิมเสมอถ้ากราฟนั้นเป็น acyclic

เราสามารถทดสอบว่ากราฟเป็น strongly connected หรือไม่ด้วยการทำ depth-first searches สองครั้ง และถ้ามันไม่เป็น strongly connected เราจะได้เซตย่อยของ vertices ที่เป็น strongly connected ในกลุ่มของมันเอง

เริ่มด้วยการทำ depth-first search กับกราฟ G ที่เป็นอินพุต กำหนดหมายเลขให้แก่ vertices ของ G เรียงลำดับตามลำดับ postorder traversal ที่เกิดใน depth-first spanning forest (คือตัวเลขตัวหลังที่แสดงในโนดของทรีในรูปที่ 9.72) จากนั้นให้กลับทิศทางลูกศรของ edges ทั้งหมดใน G สร้างเป็นกราฟ Gr กราฟในรูปที่ 9.74 คือ Gr (ตัวเลขในโนดคือหมายเลข postorder traversal) ของกราฟ G ในรูปที่ 9.72

เราจบอัลกอริทึมด้วยการทำ depth-first search ในกราฟ Gr,โดยให้เริ่มต้น depth-first search ใหม่ที่โนดที่มีหมายเลขสูงสุดของโนดที่มีอยู่เสมอ นั่นคือ เริ่มต้นทำ depth-first search ของ Gr ที่ vertex G ซึ่งมีหมายเลข 10 (ค่าสูงสุด) ซึ่งไม่สามารถเดินท่องไปโนดไหนได้ ดังนั้นจึงเริ่มใหม่ที่โนด H (หมายเลข 9 เป็นค่าสูงสุดของโนดที่เหลือ) ซึ่งสามารถเดินท่องไปได้ผ่าน I และ J จากนั้นเริ่มโนดใหม่ที่ B และท่องผ่านไปที่ A, C, และ F ต่อไปเป็นการเรียกใช้ dfs(D) และสุดท้ายคือ dfs(E) รูปที่ 9.75 แสดง depth-first spanning forest ของ Gr ที่ได้ ทรีแต่ละทรีใน depth-first spanning forest ของรูปที่ 9.74 คือส่วนที่เป็น strongly connected ซึ่งก็คือ {G}, {H, I, J}, {B, A, C, F}, {D}, และ {E} แสดงให้เห็นในรูปที่ 9.76

อัลกอริทึมนี้ให้คำตอบที่ถูกต้องได้ก็เนื่องจาก ถ้าโนด 2 โนดคือ v และ w อยู่ใน strongly connected component เดียวกันซึ่งก็หมายความว่ามีเส้นทางเดินจาก v ไป w และจาก w ไป v ปรากฏอยู่ในกราฟเริ่มต้น G และภายใน Gr ด้วย และถ้าหากว่า vertex ทั้ง 2 คือ v และ w ไม่อยู่ใน Depth-first spanning tree เดียวกันใน Gr ก็หมายความว่ามันไม่อยู่ใน strongly connected component เดียวกัน

ในการพิสูจน์ว่าอัลกอริทึมนี้ใช้ได้นั้น เราต้องแสดงให้เห็นว่าถ้าโนด 2 โนด v และ w ปรากฏอยู่ใน Depth-first spanning tree Gr เดียวกัน มันจะต้องมีเส้นทางจาก v ไป w และจาก w ไป v และลักษณะเช่นเดียวกันเราสามารถแสดงให้เห็นว่าถ้า x เป็นโนดรากของ Depth-first spanning tree Gr ที่มี v อยู่ก็หมายความว่าจะมีเส้นทางหนึ่งจาก x ไปยัง v และจาก v ไปยัง x ด้วยตรรกะเดียวกันนี้เมื่อใช้กับ w ก็หมายความว่าจะมีเส้นทางหนึ่งจาก x ไปยัง w และจาก w ไปยัง x

จากที่กล่าวมาก็หมายความว่าจะมีเส้นทางจาก v ไป w และจาก w ไป v (ด้วยการผ่านไปทาง x) เนื่องจาก v อยู่ตามหลัง x ใน Gr คือมีเส้นทางจาก x ไปยัง v ใน Gr และดังนั้นจึงมีเส้นทางจาก v ไป x ใน G ยิ่งกว่านั้น เนื่องจาก x เป็นรากมันจึงมีหมายเลข postorder ที่สูงกว่า ดังนั้นในระหว่างการทำ depth-first search ครั้งแรกนั้นการทำงานประมวลผล v ต้องเสร็จสิ้นการทำงานที่ x เนื่องจากมีเส้นทางหนึ่งจาก v ไปยัง x ก็หมายความว่า v อยู่ตามหลัง x ใน spanning tree ของ G มิฉะนั้นแล้วการทำงานที่ v ต้องเสร็จสิ้นหลัง x นี่ก็หมายความว่ามีเส้นทางจาก x ไปยัง v ใน G นั่นเอง