โครงสร้างข้อมูลแบบกราฟ (Graphs)

โครงสร้างข้อมูลกราฟ
        กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูป และการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
      กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้
กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้
G = ( V , E )
G คือ กราฟ
V คือ กลุ่มของ vertex
E คือ กลุ่มของ edge
ศัพท์ที่เกี่ยวข้อง
1.เวอร์เทก (Vertex)  หมายถึง  โหนด
2.เอดจ (Edge)        หมายถึง  เส้นเชื่อมของโหนด
3.ดีกรี (Degree)      หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด
4.แอดจาเซนท์โหนด (Adjacent Node)    หมายถึง โหนดที่มีการเชื่อมโยงกัน
ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

กราฟ (GRAPH)
                กราฟ (Graph) เป็นโครงสร้างที่แทนความสัมพันธ์ระหว่างข้อมูลที่มีข้อมูลจำกัดน้อย ความสัมพันธ์ที่ไม่มีจำกัดว่าต้องเป็นตามลำดับชั้น หรือข้อมูลต้องเรียงจากซ้ายไปขวา
                กราฟ (Graph) หมายถึง เซตของสิ่งที่เรียกว่า โหนด (Note หรือ Vertex) และเส้นเชื่อม (Edge) “โหนด” คือ สมาชิกของความสัมพันธ์ระหว่างโหนด 2 โหนด จะเขียนอยู่ในรูปของคู่อันดับ (a , b)

                กราฟแบ่งออกเป็น 2 ประเภท คือ
                กราฟไม่มีทิศทาง (Undirected Graph) เป็นกราฟที่มีเส้นเชื่อมระหว่างโหนด 2 ตัวไม่มีทิศทาง

                  กราฟมีทิศทาง (Directed Graph) เป็นกราฟที่มีเส้นเชื่อมระหว่างระบุทิศทางกำกับอยู่

           จากกราฟรูปที่ 8.2 เป็นภาพแสดงความสัมพันธ์แบบไม่มีทิศทาง เส้นเชื่อมระหว่างโหนด 2 ตัวไม่มีทิศทางระบุไว้ ดังนั้นจากโหนด A ไปโหนด B มีความหมายเหมือนโหนด B ไปโหนด A ในกราฟมีทิศทาง รูปที่ 8.3 เส้นเชื่อมโหนดมีทิศทางกำกับอยู่ ความหมายจากโหนด A ไปโหนด B ไม่เหมือนกับ B ไป A 

             เส้นทางเดินในกราฟ

                การกำหนดทางการเดินในกราฟมีเชื่อมต่อกัน 2 ลักษณะ คือ ต่อกันโดยทางตรง (Directly Connection) และต่อกันแบบทางอ้อม (Indirectly Connected) ซึ่งการเชื่อต่อของลักษณะทางอ้อม และเส้นเชื่อมที่เข้าและออกจากแต่ละโหนดจะเรียกว่า ดีกรี (Degree) ดังนั้น ดีกรีจะ หมายถึง จำนวนของเส้นเชื่อมที่ต่อโดยตรงกับโหนดนั้น ๆ มี 2 ชนิด คือ เอาต์ดีกรี (Outdegree) เป็นเส้นที่ออกจากโหนด และอินดีกรี (Indegree) เป็นเส้นที่เข้ามายังโหนดนั้น ๆ