การประกาศโครงสร้างกราฟ (Graph Declarations)

การประกาศโครงสร้างกราฟ (Graph Declarations)

ตัวอย่าง แสดงการประกาศโครงสร้างข้อมูลของกราฟในภาษาซี โดยมีจำนวนเวอร์เทกซ์

สูงสุดไม่เกิน 10 ใช้สำหรับกราฟที่มีน้ำหนักและมีทิศทาง

#define MAXVERTICE 10 /*จำนวนเวอร์เทกซ์ทั้งหมด*/

#define NULLEDGE 0 /* กรณีไม่ทีเอดจ์ ค่าเอดจ์เป็นศูนย์*/

#define STRING30 30

#define NOT_FOUND -1

typedef int EdgeValue; /*เก็บน้ำหนักของเอดจ์*/

typedef char * String;

typedef struct

{

Int numVertices;

char vertexList [MAXVERTICES] [STRING30];

} VertexListtypeType;

typedef struct

{

VertexListType vertices;

EdgeValue edges [MAXVERTICES] [MAXVERTICES];

} GraphType;

GraphType graph;

การประกาศข้างต้น สามารถวาดเป็นภาพของโครงสร้างกราฟดังนี้

โครงสร้างกราฟที่ประกาศนี้ ประกอบด้วย 2 ฟิลด์หลัก คือ

1. ฟิลด์ของเวอร์เทกซ์ (Vertices) โดยที่ส่วนของเวอร์เทกซ์นี้ยังมีโครงสร้างซ่อนอยู่ภายใน และโครงสร้างในยังประกอบด้วย 2 ฟิลด์ย่อย คือ

ก. ชื่อของเวอร์เทกซ์ (vertexList) ซึ่งได้ประกาศเป็นอาร์เรย์ของสตริงเพื่อใช้เก็บชื่อของเวอร์เทกซ์ เช่น ชื่อจังหวัด เราสามารถอ้างอิงฟิลด์ได้ดังนี้

graph.vertices.vertexList [0]

graph.vertices.vertexList [1]

graph.vertices.vertexList [2]

graph.vertices.vertexList [MAXVERTICES-1]

ข. จำนวนของเวอร์เทกซ์ (numVertices) ซึ่งได้ประกาศเป็นจำนวนเต็มเพื่อใช้เก็บจำนวนของเวอร์เทกซ์ทั้งหมด เราอ้างอิงฟิลด์นี้ด้วย graph.vertices.numVertices

2. ฟิลด์ของเอดจ์ (edges) ซึ่งได้ประกาศเป็นอาร์เรย์ 2 มิติ ใช้เก็บเอดจ์ที่บ่งบอกถึงเวอร์เทกซ์ใดเชื่อมโยงกับเวอร์เทกซ์ใด ค่าของเอดจ์เป็นชนิดจำนวนเต็ม เพื่อใช้เก็บน้ำหนักของเอดจ์ หากเป็นกราฟที่ไม่มีน้ำหนัก ส่วนนี้อาจเก็บเป็นชนิดบูลีนก็ได้ โดยให้เก็บค่า TURE หากพบว่ามีเอดจ์โยงระหว่างเวอร์เทกซ์และเก็บค่า FALSE หากไม่พบเอดจ์โยงระหว่างเวอร์เทกซ์หรืออาจใช้ค่าจำนวนเต็ม 1 หรือ 0 แทนค่าบูลีน TURE/FALSE ก็ได้

การแทนโครงสร้างกราฟด้วยอาร์เรย์ที่แสดงให้เห็นถึงเส้นทางการเดินทางระหว่างจังหวัด

โดยใช้กราฟจากตัวอย่างข้อ 9.5

อาร์เรย์ช่องที่ 9 ว่างเปล่า  แสดงว่ายังไม่ได้กำหนดค่าให้ (Undefined)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s