การแทนกราฟด้วยวิธีอื่น (Other Graph Implementations)

13 พ.ย. 2008 ให้ความเห็น

by shutchon in Algorithm

การแทนกราฟด้วยวิธีอื่น (Other Graph Implementations)

ที่ผ่านมาเราแทนกราฟด้วยเมทริกซ์ข้างเคียง (Adjacency Matrix) โดยใช้อาร์เรย์ 2 มิติแทน ซึ่งมีข้อดีคือ ง่าย แต่ในบางกรณีอาจต้องใช้เนื้อที่ในการจัดเก็บมากเกินความจำเป็น โดยเฉพาะในกรณีที่กราฟนั้นประกอบด้วยเวอร์เทกซ์จำนวนมาก แต่กลับมีเอดจ์จำนวนน้อย ดังตัวอย่างของกราฟต่อไปนี้

หากนำกราฟข้างต้นมาแทนด้วยเมทริกซ์ข้างเคียงจะได้ลักษณะของอาร์เรย์ 2 มิติ ทีมีค่า 0 เก็บในอาร์เรย์จำนวนมาก ดังนี้

เมทริกซ์ที่ประด้วยค่าที่เป็น 0 จำนวนมาก ดังตัวอย่างข้างต้น เรียกว่า สปาร์เมทริกซ์ (Sparse Matrix)

กราฟที่มีเวอร์เทกซ์มากแต่มีเอดจ์น้อย หากนำมาแทนด้วยเมทริกซ์จะเกิดปัญหาในลักษณธเป็นสปาร์เมทริกซ์ ซึ่งไม่ก่อให้เกิดประโยชน์เต็มที่ เพราะใช้เนื้อที่จัดเก็บมากเกินความจำเป็น

ลิสต์ข้างเคียง (Adjacency List)

การแทนกราฟด้วยลิงค์ลีสต์อย่างเดียว ดังเช่นกรณีของสปาร์สเมทริกซ์อาจดูยุ่งยากมากเมื่อเปรียบเทียบกับการใช้เมทริกซ์ข้างเคียง วิธีลดความยุ่งยากและลดพื้นที่อีกวิธีหนึ่ง คือ การใช้อาร์เรย์ผสมกับพอยเตอร์ ซึ่งวิธีการนี้เรียกว่า ลิสต์ข้างเคียงหรือลิสต์ประชิด (Adjacency List) โดยใช้ส่วนของเวอร์เทกซ์เก็บไว้ในอาร์เรย์ และมีพอยเตอร์ชี้ไปยังรายการของเวอร์เทกซ์ข้างเคียง

ตัวอย่าง การแทนกราฟที่ใช้มาด้วยลิสต์ข้างเคียง โดยที่ในแต่ละโหนดในลิงค์ลิสต์ประกอบด้วย 3 ฟิลด์ คือ index ของเวอร์เทกซ์ที่ชี้ไป น้ำหนักของเอดจ์ และพอยเตอร์ที่เชื่อมโยงโหนด

ต้นไม้ทอดข้าม (Spanning Trees)

13 พ.ย. 2008 ให้ความเห็น

by shutchon in Algorithm

ต้นไม้ทอดข้าม (Spanning Trees)

ต้นไม่ (Tree) เป็นเซตย่อย (Subset) ของกราฟไม่มีทิศทาง ดังนั้นเราจึงสามารถสร้างต้นไม้จากกราฟได้ กราฟที่จะนำมาสร้างต้นไม้ จะต้องเชื่อมต่อกัน (Connected) ส่วนต้นไม้ที่ได้จะต้องประกอบด้วยทุกเวอร์เทกซ์จากกราฟ โหนดในต้นไม้ต้องเชื่อมต่อกัน และต้องไม่เป็นวง (Acyclic) ต้นไม้ที่สร้างจากกราฟนี้เรียกว่า ต้นไม้ทอดข้าม (Spanning Tree)

ต้นไม้ทอดข้ามน้อยสุด (Minimum Spanning Trees)

จากตัวอย่างข้างต้นจะเห็นว่า เราสามารถสร้างต้นไม้ทอดข้ามจากกราฟได้หลายต้น แต่ที่อยู่ในความสนใจคือ กรณ๊ที่สร้างต้นไม้ทอดข้ามจากกราฟแบบมีน้ำหนัก (Weighted Graph) โดยให้มีน้ำหนักรวมของเอดจ์น้อยที่สุด ซึ่งเราเรียกต้นไม้นี้ว่า ต้นไม้ทอดข้ามน้อยสุด (Minimum Spaning Tree)

อัลกอริทึมของพริม (Prim’s Algorithm)

อัลกอริทึมของพริมใช้วิธีการเชิงละโมบเช่นเดียวกับอัลกอริทึมของดิจสตราโดยเริ่มต้นจาก

เวอร์เทกซ์ที่กำหนดแล้วหาเวอร์เทกข้างเคียง เรียงตามค่าน้ำหนักของเอดจ์โดยใช้ Priority Queue เลือกเวอร์เทกซ์ที่มีค่าน้ำหนักของเอดจ์น้อยที่สุด แล้วหาเวอร์เทกซ์ข้างเคียงของเวอร์เทกซ์นี้ใส่ไว้ใน Priority Queue ทำอย่างนี้ไปเรื่อย ๆ จนครบทุกเวอร์เทกซ์

ซึ่งแนวทางข้างต้นสามารถนำมาเขียนเป็นอัลกอริทึมได้ดังนี้

initMarks (graph)

clearPriorityQ (pqueue)

enPQ (pqueue, startVertex)

do

dePQ (pqueue, vertex)

if (NOT vertexMarked)

markVertex (vertex)

getAdjacencyVertices (adjList)

enPQ (pqueue, adjList)

while (NOT emptyPQ (pqueue))

จะเห็นได้ว่าอัลกอริทึมของพริม เพื่อหาต้นไม้ทอดข้ามน้อยที่สุดเกือบเหมือนอัลกอริทึมเพื่อหาเส้นทางสั้นที่สุดทุกประการ แต่ในการหาเส้นทางที่สั้นที่สุด ต้องปรับน้ำหนัก (updateWeiht) ในขณะที่การหาต้นไม้ทอดข้ามน้อยที่สุดไม่ต้อง

วิธีการสร้างต้นไม้ทอดข้ามน้อยสุด

ตัวอย่างการสร้าต้นไม้ทอดข้ามน้อยสุด จากกราฟที่กำหนดให้ โดยเริ่มจากเวอร์เทกซ์ A

การท่องเข้าไปในกราฟ (Traversing a Graph)

12 พ.ย. 2008 ให้ความเห็น

by shutchon in Algorithm

การท่องเข้าไปในกราฟ (Traversing a Graph)

เช่นเดียวกับในกรณีของต้นไม้ (Tree) ที่มีการท่องเข้าไปเพื่อหาข้อมูลที่เก็บในโครงสร้างต้นไม้ เราก็มีการท่องเข้าไปในกราฟเพื่อหาข้อมูลที่เก็บในโครงสร้างกราฟเช่นกัน แต่จะต่างกันที่โครงสร้างต้านไม้ต้องเริ่มต้นท่องจากที่รูท (root) เสมอ แต่ในกราฟสามารถเริ่มจากเวอร์เทกซ์ใดก็ได้

การท่องเข้าไปในกราฟมี 2 รูปแบบ คือ

1. แบบการค้นหาในแนวลึก ( Depth – First Search)

2. แบบการค้นหาในแนวกว้าง ( Breadth – First Search)

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

12 พ.ย. 2008 ให้ความเห็น

by shutchon in Algorithm

การดำเนินการกับกราฟ (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.

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

12 พ.ย. 2008 ให้ความเห็น

by shutchon in Algorithm

การประกาศโครงสร้างกราฟ (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)

กาแทนกราฟด้วยเมทริกซ์หรืออาร์เรย์สองมิติ

12 พ.ย. 2008 ให้ความเห็น

by shutchon in Algorithm

กาแทนกราฟด้วยเมทริกซ์หรืออาร์เรย์สองมิติ

(Implementation Of a Graph as a Matrix or Two – Dimensional Array)

ในคอมพิวเตอร์ เราสามารถสร้างกราฟด้วยเมทริกซ์ข้างเคียง (Adjacency Matrix) หรือ

เมทริกซ์ประชิด ซึ่งเป็นอาร์เรย์ 2 มิติ เพื่อใช้สำหรับเก็บค่าของเอดจ์

ตัวอย่าง การสร้างกราฟไม่มีทิศทางด้วยอาร์เรย์ 2 มิติ

จากกราฟข้างต้น  สามารถเก็บในเมทริกซ์ข้างเคียงหรืออาร์เรย์ได้ดังนี้

กราฟที่มีน้ำหนัก (Weighted Graphs)

12 พ.ย. 2008 ให้ความเห็น

by shutchon in Algorithm

กราฟที่มีน้ำหนัก (Weighted Graphs)

กราฟที่มีน้ำหนัก คือ กราฟที่แต่ละเอดจ์จะมีค่าบ่งบอกถึงความหมายอย่างใดอย่างหนึ่งอยู่

ด้วย ซึ่งค่านี้อาจหมายถึง ระยะทาง ความเร็ว เวลาเดินทาง ค่าโดยสาร ฯลฯ กราฟที่มีน้ำหนัก สามารถนำมาประยุกต์ใช้กับงานที่จำเป็นต้องคำนึงถึงค่าของเอดจ์

ตัวอย่าง กราฟแสดงเส้นทางการเดินทางระหว่างเมือง โดยที่แต่ละเอดจ์ของกราฟจะมีค่าน้ำหนัก ซึ่งแสดงถึงระยะทางระหว่างเมือง

จากกราฟข้างต้นใช้เวอร์เทกซ์แทนจังหวัด และเอดจ์แทนระยะทางระหว่างจังหวัด หากต้องการเดินทางจากชลบุรีไปปราจีนบุรี เราต้องมองหาเส้นทางการเดินทางระหว่างสองจังหวัดนี้ พบว่ามีหลายเส้นทางที่สามารถใช้เดินทางจากชลบุรีไปปราจีนบุรี เช่น

ชลบุรี – ฉะเชิงเทรา – ปราจีนบุรี รวมระยะทาง 119 กม.

ชลบุรี – ฉะเชิงเทรา – นครนายก – ปราจีนบุรี รวมระยะทาง 172 กม.

ชลบุรี – ระยอง – ฉะเชิงเทรา – ปราจีนบุรี รวมระยะทาง 314 กม.

-

-

-

ฯลฯ

หากเลือกเส้นทางใดเส้นทางหนึ่ง เราสามารถหาระยะทางรวมของการเดินทางนี้ได้ ด้วยการรวมค่าน้ำหนักของเอดจ์ทุกตัวที่เชื่อมโยงเส้นทางไปยังจังหวัดที่เราเลือกเดินทาง