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

กราฟ (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) เป็นเส้นที่เข้ามายังโหนดนั้น ๆ