การดำเนินการกับกราฟ (Operations on Graphs)

การดำเนินการกับกราฟ (Operations on Graphs)

เราสามารถดำเนินการกับโครงสร้างกราฟด้วยการเขียนโปรแกรมย่อยหรือโมดูลได้ดังนี้

1. การสร้างกราฟ (createGraph)

2. การเพิ่มเวอร์เทกซ์เข้าไปในกราฟ (addVertex)

3. การเพิ่มเอดจ์ (addEdge)

4. การสอบถามค่าน้ำหนักของเอดจ์ (weight)

5. การลบเวอร์เทกซ์(deleteVertex)

6. การลบเอดจ์ (deleteEdge)

การเขียนโปรแกรมย่อยสำหรับจัดการโครงสร้างกราฟ

อาศัยการประกาศโครงสร้างกราฟที่ผ่านมา เราสามารถเขียนโมดูลเพื่อปฏิบัติการบนกราฟได้ดังนี้

ข้อสังเกต

หากกราฟเป็นแบบไม่มีทิศทาง จำเป็นต้องเรียกไปที่ฟังก์ชัน addEdge 2 ครั้ง ครั้งแรกสำหรับทิศทางไป ครั้งที่สองสำหรับทิศทางกลับ

โมดูลการสอบถามค่าน้ำหนักของเอดจ์ (weight Module)

การเขียนฟังก์ชันชื่อ weight เพื่อสอบถามหาน้ำหนักของเอดจ์ fromVertex ไปยัง toVertex ซึ่งการจะหาน้ำหนักนี้ได้ เราจะต้องค้นหาตำแหน่งของเวอร์เทกซ์ทั้งสองด้วยการเรียกไปที่ฟังก์ชัน searchVertexindex

EdgeValue weight (GraphYype *g, String fromvertex,

String tovertex)

{

int fromindex, toindex;

EdgeValue wgh;

fromindex = searchVertexIndex (g, fromvertex);

toindex = searchVertexIndex (g, tovertex);

if ((fromindex = = NOT_FOUND) l l (toindex = =NOT_FOUND))

}

Printf (“invalid edge ”); /*กรณีหาเอดจ์ไม่เจอ*/

Wgh = 0; /* ค่าน้ำหนักจะเป็นศูนย์หากหาไม่พบ*/

}

else

wge = g ->edges [fromindex] [toindex];

return (wgh);

} /* weight */

โมดูลการลบเอดจ์ (deleteEdge Module)

การเขียนฟังก์ชันชื่อ deleteEdge เพื่อจัดการเอาเอดจ์ที่ระบุออกจากราฟ ซึ่งการลบเอดจ์ สามารถทำได้ง่าย ๆ ด้ยการเรียกไปที่ฟังก์ชัน addEdge แล้วทำให้ edge มีค่า 0

Void deleteEdge (GraphType *g, String fromvertex, String tovertex)

{

addEdge (g, fromvertex, tovertex, 0);

} /* deleteEdge */

โมดูลการลบเวอร์เทกซ์ (deleteVertex Module)

การเขียนฟังก์ชันชื่อ deleteVertex เพื่อจัดการเอาเวอร์เทกซ์ที่ระบุออกจากกราฟ ซึ่งการลบนี้สามารถทำได้ด้วยการค้นหาตำแหน่งของเวอร์เทกซ์ที่ต้องการลบ จากนั้นให้เลื่อนแถวขึ้น (Shift Up) โดยเริ่มจากแถวถัดจากที่ถูกลบขึ้นมาในลักษณะขยับขึ้นทีละแถวตามลำดับและเลื่อนคอลัมภ์เข้ามาทางซ้าย (Shift Left) โดยเริ่มจากคอลัมภ์ถัดจากที่ลบในลักษณะเขยิบเข้ามาทีละคอลัมภ์ตามลำดับ

void deleteVertex (GraphType *g, String vertex)

{

int index , i , j ;

/* เริ่มด้วยการหาตำแหน่งของเวอร์เทกซ์ที่ต้องการลบ */

index = searchVertexIndex (g, vertex);

if (index = = NOT_FOUND)

printf (“invalid vertex ”) ; /* หาไม่เจอ */

else

{

for (i = index; i < g -> vertices.numVertices-1; i++)

strcpy (g -> vertices. vertexList [i] , /* ขยับเวอร์เทกซ์*/

g -> vertices . vertexList [i+1]) ;

for (i = index ; i < g -> vertextices.numVertices -1 ; i++)

for ( j = 0 ; j < g -> vertices.numVertices; j++)

g -> edges [1] [j] = g ->edges [i+1] [j] ; /* ขยับแถวเอดจ์*/

for (i = index ; i < g -> vertextices.numVertices -1; i++)

for ( j = 0 ; j < g -> vertices.numVertices; j++)

g -> edges [j] [i] = g ->edges [j] [i+1]; /* ขยับคอลัมภ์เอดจ์*/

g ->vertices.numVertices- – ;

. ฟังก์ชัน addVertex นอกจากจะนำเวอร์เทกซ์ใหม่เข้าเก็บในอาร์เรย์ vertexList แล้ว ยังต้องกำหนดค่า (Initialize) เอดจ์ของเวอร์เทกซ์นี้ให้เป็นศูนย์หรือ NULLEDGE ด้วย

โมดูลการเพิ่มเอดจ์ (addEdge Module)

การเขียนฟังก์ชันชื่อ addEdge เพื่อเพิ่มเอดจ์เข้าไปในกราฟ ในส่วนเมทริกซ์ edges ก่อนจะเพิ่มเอดจ์ได้ เราต้องค้นหาตำแหน่งของเวอร์เทกซ์ใน vertexList ก่อน ซึ่งตำแหน่งของเวอร์เทกซ์ที่ต้องการหามี 2 ค่า คือ ตำแหน่งของ fromVertex และ toVertex ซึ่งจะเป็นตำแหน่งของแถว (row) และคอลัมภ์ (column) ในเมทริกซ์ ด้วยเหตุนี้ในฟักช์ชัน addEdge จึงต้องมีฟังก์ชัน searchVertwxIndex เพื่อใช้หาตำแหน่งของเวอร์เทกซ์ดังกล่าว

int searchVertexKndex (GraphType *g, String vertex)

/* ถ้าเจอคือตำแหน่งใน vertexList ถ้าไม่เจอคือค่า -1 (NOT_FOUND) */

{

int index

index = 0;

while ((strcmp (g -> vertices.vertexList [index] , vertex)) &&

(index < g -> vertices.numVertices))

Index ++; /* ลูปหาตำแหน่งของเวอร์เทกซ์ */

if (index >= g ->vertices.numVertices)

index = NOT_FOUND ; /* กรณีหา vertex ไม่เจอ ให้คืนค่า -1 */

return (index); /* ถ้าไม่เจอ vertex คือตำแหน่ง index */

} /* searchVertexIndex */

ฟังก์ชัน searchVertexIndex จะถูกเรียกใช้งานโดยฟังก์ชัน addEdge

void addEdge (GraphYype *g, String fromVertex, String toVertex,

EdgejValue weigh)

{

int fromindex , toindex;

/* หาตำแหน่งของเวอร์เทกซ์ ในแถว (row) และคอลัมภ์ */

fromindex = searchVertexIndex (g, fromVertex);

toindex = searchVertexIndex (g, toVertex);

if ((fromindex= = NOT_FOUND) l l (toindex = = NOT_FOUND))

printf ( “invalid edge ”);

else /* เพิ่มน้ำหนักของเอดจ์*/

g -> edges [fromindex] [toindex] = weigh;

} */ addEdge*/

โมดูลการสร้างกราฟ (createGraph Module)

การเขียนฟังก์ชันชื่อ createGraph เพื่อกำหนดค่าเริ่มแรกให้กราฟว่างเปล่า

void createGraph (GraphType *g)

{

g->vertices.numVertices = 0;

} /* creatGraph */

ฟังก์ชัน createGraph ได้กำหนดค่าให้ฟิลด์ numVertices มีค่าศูนย์ ซึ่งแสดงว่าเริ่มแรกยังไม่มีเวอร์เทกซ์ใด ๆ เก็บใน graph.vertices และในส่วนของ graph.edges ก็ยังไม่มีเอดจ์ใดๆ

ภายหลังการสร้างกราฟเปล่าขึ้นมาแล้ว เราสามารถเพิ่มเวอร์เทกซ์ (addvertex) เข้าไปในกราฟด้วยโมดูลต่อไปนี้

โมดูลการเพิ่มเวอร์เทกซ์เข้าไปในกราฟ (addVertex Module)

การเขียนฟังก์ชั่นเพื่อ addVertex เพื่อดำเนินการนำชื่อของเวอร์เทกซ์เข้าเก็บในช่องว่างถัดไปของอาร์เรย์ vertexList

void addVertex (GraphType *g, String newVertex)

{

int i ;

strcpy (g -> vertices.vertexList [g -> vertices.

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