CoE KKU

Graph $G = (V, E)$ ประกอบด้วยเซตของ vertices V, และเซตของ edges E แต่ละ edge คือคู่ $(v,w)$ เมื่อ $v,w ∈ V$ บางครั้งก็เรียก Edges ว่า arcs

ถ้า edge เป็นแบบคู่อันดับก็จะได้กราฟเป็นแบบ directed graph เรียกสั้น ๆ ว่า digraphs

vertex $w$ เป็น adjacent กับ $v$ ถ้า (iff) $(v,w) ∈ E$ สำหรับ undirected graph ที่มี edge $(v,w)$ นั่นคือมี $(w,v)$ ดังนั้น $w$ เป็น adjacent กับ $v$ และ $v$ เป็น adjacent กับ $w$ บางครั้ง edge อาจจะมีองค์ประกอบเพิ่มเติมเข้ามาและเรียกว่า weight หรือ cost

Path หนึ่ง ๆ ภายในกราฟ คือลำดับของ vertices $w_1, w_2, w_3, . . . , w_N$ ที่ $(w_i, w_{i+1}) ∈ E$ สำหรับ 1 ≤ i < N ความยาว (length) ของ path คือ จำนวน edges บน path นั้นซึ่งมีค่าเท่ากับ N – 1 กรณีที่กราฟมี edge $(v,v)$ จาก vertex ไปยังตัวมันเองแล้ว เรียก path $v$, $v$ ว่า loop กราฟที่เราจะศึกษากันโดยทั่วไปแล้วไม่มี loop เส้นทางที่เรียกว่า simple path คือ เส้นทางที่มี vertices ทั้งหมดไม่ซ้ำกัน ยกเว้นตัวแรกและตัวสุดท้ายของเส้นทางนั้นที่อาจเป็นตัวเดียวกันได้

Cycle ภายใน directed graph คือ path ที่มี length อย่างน้อยเท่ากับ 1 ซึ่งมี $w_1 = w_N$; และ cycle นี้เรียกว่า simple cycle ถ้า path เป็น simple path สำหรับ undirected graphs แล้วกรณีนี้ต้องเป็นคนละ edge กัน กราฟแบบ directed graph เรียกว่าเป็นกราฟแบบ acyclic ถ้ามันไม่มี cycles และมักใช้อักษรย่อด้วยคำว่า DAG

กราฟแบบ undirected graph เป็นแบบ connected ถ้ามีอย่างน้อยหนึ่งเส้นทางจากทุก ๆ vertex ไปยัง vertex อื่น ๆ ได้ สำหรับ directed graph ที่มีคุณสมบัติดังกล่าวนี้จะเรียกว่า strongly connected ถ้า directed graph ไม่เป็นกราฟแบบ strongly connected แต่ถ้ายกเลิกทิศทางเสียแล้วทำให้มันเป็นกราฟแบบ connected ได้ก็จะเรียกกราฟนี้ว่าเป็นกราฟแบบ weakly connected กราฟที่เป็น complete graph คือกราฟที่มี edge เชื่อมต่อระหว่าง vertices ทุก ๆ คู่

สนามบินในระบบเส้นทางการบินเป็นตัวอย่างหนึ่งที่เราสามารถจำลองแบบได้ด้วยกราฟ โดยกำหนดให้สนามบินแต่ละแห่งแทนด้วย vertex หนึ่ง และ vertices 2 vertices เชื่อมต่อด้วย edge หนึ่งถ้าเป็นการบินตรงระหว่างสนามบินทั้งสอง แต่ละ edge อาจประกอบด้วย weight ซึ่งอาจจะหมายถึงเวลาที่ใช้ในการบิน หรือระยะทาง หรือค่าตั๋วก็ได้ และกราฟที่ใช้ก็อาจจะเป็นแบบ directed graph เนื่องจากระยะเวลาที่ใช้ในการบินหรือค่าตั๋วสำหรับการบินไปและกลับไม่เท่ากัน

การจราจรบนถนนก็สามารถจำลองได้ด้วย graph เช่นเดียวกัน จุดตัดของถนนสามารถแทนได้ด้วย vertex หนึ่งและถนนแต่ละเส้นก็คือ edge โดยที่ edge costs อาจหมายถึงขีดจำกัดความเร็ว หรือจำนวนช่องจราจรก็ได้

ในที่นี้จะกล่าวถึง directed graphs (ส่วน undirected graphs ก็มีลักษณะคล้ายกัน)สมมุติให้เราสามารถกำหนดหมายเลขให้แก่ vertices ได้ โดยเริ่มจาก 1 กราฟในรูปที่ 9.1 มี 7 vertices 12 edges

วิธีอย่างง่ายในการแสดงกราฟ คือการใช้อะเรย์ 2 มิติซึ่งเรียกว่า adjacency matrix ( a[ ][ ] ) โดยสำหรับแต่ละ edge (u, v) กำหนดให้ a[u][v] เป็น true ถ้าไม่มี edge ก็ให้เป็น false กรณีที่มี weight ด้วยก็กำหนดให้ a[u][v] มีค่าเท่ากับ weight และให้ใช้ค่า weight สูงมาก ๆ หรือ ต่ำมาก ๆ เป็น sentinel ที่หมายถึงไม่มี edges อยู่ เช่น ถ้าเป็นกรณีใช้กราฟแสดงเส้นทางบิน เราแทนเส้นทางที่ไม่มีการบินด้วยค่า ∞

ถึงแม้ว่าการใช้ adjacency matrix ดูจะง่ายในการใช้งานแต่ต้องใช้เนื้อที่ $\Theta(|V|^2)$, ซึ่งอาจจะไม่เหมาะสมกรณีที่ถ้ากราฟนั้นมี edges จำนวนไม่มาก เรามักจะใช้ adjacency matrix ถ้ากราฟนั้นเป็น dense graph กล่าวคือ $|E| = \Theta(|V|^2)$ ซึ่งกรณีส่วนใหญ่แล้วเราจะพบกับเหตุการณ์แบบนี้น้อยมาก

เช่นถ้าเราใช้กราฟเป็นแบบจำลองแผนที่ถนนในเมืองซึ่งถนนเกือบทั้งหมดตัดระหว่างทิศเหนือ-ใต้และตะวันออก-ตะวันตก ดังนั้นจุดตัดของถนนแต่ละจุดก็จะเชื่อมต่อระหว่างถนน 4 สายโดยประมาณและถ้าใช้กราฟแบบ directed graph และถนนทุกสายเป็นแบบ 2-ways ก็จะได้ว่า $|E| ≈ 4 |V|$ ถ้าถนนมีจุดตัด 3,000 จุด กราฟก็จะต้องมี 3,000 vertices และมี edge เป็นจำนวน 12,000 edges ซึ่งทำให้ต้องใช้อะเรย์ขนาด 9,000,000 เซลล์ และเกือบทั้งหมดของเซลล์ในอะเรย์มีค่าเป็น 0 สภาพเช่นที่กล่าวนี้เป็นสิ่งที่ไม่พึงประสงค์เพราะเหตุว่าเราต้องการให้โครงสร้างข้อมูลที่เราใช้นั้นเป็นตัวแทนของข้อมูลที่มีอยู่จริงเท่านั้น

ถ้ากราฟไม่เป็นกราฟแบบ dense graph (เรียกว่า graph แบบ sparse) วิธีการที่ดีกว่าการใช้ matrix ก็คือการใช้ adjacency list คือแต่ละ vertex มี list ของ adjacent vertices ทั้งหมดของมัน และใช้เนื้อที่ขนาด $O(|E| + |V|)$ ซึ่งเรียกว่าเป็น linear ในเทอมของขนาดของกราฟ จากรูปที่ 9.2 โครงสร้างทางด้านซ้ายเป็นอะเรย์ของ header เท่านั้น กรณีที่ edges มีค่าของ weights จะเพิ่มเติมข้อมูลนี้ลงในโนดของ list ด้วย

node V= {1,2,3,4,5,6,7} edge E= { (1,2), (1,4), (1,3), (2,4), (2,5), (3,6), (4,6), (4,7), (4,3), (5,4), (5,7), (7,6)}	\begin{bmatrix}0&1&1&1&0&0&0\\0&0&0&1&1&0&0\\0&0&0&0&0&1&0\\0&0&1&0&0&1&1\\0&0&0&1&0&0&1\\0&0&0&0&0&0&0\\0&0&0&0&0&1&0\\\end{bmatrix}
Data file	Adjacency matrix	Adjacency list

Adjacency lists เป็นวิธีมาตรฐานที่ใช้ในการจำลองรูปแบบแทน graphs สำหรับ Undirected graphs แล้ว edge แต่ละ edge (u, v) จะปรากฏอยู่ใน lists สองแห่ง การทำงานพื้นฐานที่ต้องใช้ในอัลกอริทึมของกราฟ คือการหา vertices ที่เป็น adjacent กับ vertex v ที่กำหนด และสามารถทำได้โดยใช้เวลาที่แปรผันตามจำนวน vertices ที่พบจากการ scan ไปตาม adjacency list

สารสนเทศที่เกี่ยวข้องกับ vertex รวมทั้งลิสต์ของ adjacent vertices จะได้รับการจัดเก็บอยู่ในออบเจ็กต์ชนิด Vertex ในปัญหาจริงแล้วจะมีต้องชื่อสำหรับ vertices ในกราฟซึ่งเราไม่สามารถรู้ได้ในขณะ compile-time ดังนั้นจึงต้องมีกระบวนการในการ map ชื่อเหล่านั้นไปเป็นออบเจ็กต์ Vertex โดยปกติแล้วก็จะใช้ตารางแฮชที่ประกอบด้วยชื่อที่ใช้เป็น key และ reference ที่ใช้อ้างถึง Vertex เมื่ออ่านค่าจากกราฟก็จะมีการสร้าง Vertex ใหม่ขึ้น เมื่อมีการอินพุตแต่ละ edge เข้ามานั้นเราจะตรวจสอบว่า vertex แต่ละตัวของทั้งสองนั้นผ่านการตรวจมาก่อนแล้วหรือไม่ ถ้ามันเคยผ่านการตรวจแล้วเราก็จะใช้ Vertex นั้น ถ้าไม่เราก็จะสร้างออบเจ็กต์ Vertex ขึ้นใหม่และบรรจุชื่อและคู่ของออบเจ็กต์ Vertex ลงในตารางแฮช

ในบทนี้จะได้แสดงคำสั่งโปรแกรมในรูปของ Pseudocode เพื่อจะได้มีความชัดเจนในการแสดงอัลกอริทึมและเป็นการประหยัดเนื้อที่ด้วย