การแทนโครงสร้างข้อมูลกราฟ

การแทนโครงสร้างข้อมูลกราฟ

การแทนโครงสร้างข้อมูลกราฟเป็นการแทนความสัมพันธ์ที่เกิดขึ้นจากกราฟด้วยรูปแบบที่สามารถนำไปประมวลผลด้วยคอมพิวเตอร์ แบ่งออกเป็น 2 วิธีคือ

1. Adjacency Matrices คือ การแทนด้วยอาร์เรย์ขนาด N x N ด้วยการกำหนดหมายเลข 1 ในแถวที่ i และสดมภ์ที่ j ในเมตริกซ์ โดยที่ i และ j เป็นหมายเลขโหนดของกราฟ ถ้า Aij มีค่าเป็น 1 หมายถึง มีความสัมพันธ์ระหว่างโหนด i ไปโหนด j (มีเส้นเชื่อมจาก i ไป j) ถ้า Aij มีค่าเป็น 0 หมายถึง ไม่มีความสัมพันธ์ระหว่างโหนด i ไปโหนด j ไม่มีเส้นเชื่อมจาก i ไป j )



2. Node Directory หรือ Linked list จากการแทนกราฟด้วยอาร์เรย์จะต้องมีการเก็บข้อมูลเส้นทางเชื่อมต่อทุก ๆ เส้นทางที่เกิดขึ้น ทำให้สิ้นเปลืองเนื้อที่ของหน่วยความจำ เนื่องจากต้องมีการจอง

เนื้อที่ ที่ไม่ได้ใช้ไว้ (ค่าเป็น 0 ) แต่การแทนข้อมูลด้วยโครงสร้างแบบ Node Directory จะเก็บข้อมูลที่มีความสัมพันธ์กัน (ค่าไม่เป็น 0) การหาตำแหน่งของข้อมูลทำได้ง่ายและรวดเร็วกว่า การจัดเก็บข้อมูลจะมีลักษณะของการจัดเก็บข้อมูลที่จัดเรียงต่อเนื่องกันเป็นชุด และข้อมูลแต่ละชุดจะถูกเรียกว่า โหนด (Node)

ซึ่งมี 2 แบบ คือ Node Directory และ Multi-list

Node Directory

การแทนกราฟด้วยโครงสร้างข้อมูลแบบ Node Directory ประกอบด้วยข้อมูล 2 ส่วน คือ

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

- Edge Information คือ ส่วนของข้อมูลตำแหน่งที่อยู่ของโหนดต่อไป ซึ่งประกอบด้วย เซ็ตของโครงสร้างข้อมูลของการเชื่อมโยง คือชื่อโหนด (Node Identifier) และ พอยน์เตอร์ที่ชี้ไปยังสมาชิกตัวถัดไป











Multi-list

การแทนกราฟด้วย Multi-list ประกอบด้วย 2 ส่วนคือ ส่วนที่เป็น Node Directory ที่จัดเก็บข้อมูล

จริง ๆ และส่วนของ Edge Information ซึ้งข้อมูลในส่วนของ Edge Information ซึ้งข้องมูลในส่วนของ Edge Information จะประกอบด้วยข้อมูล 4 ส่วน คือ (1) ข้อมูลชื่อของโหนด i (Vi) (2) ตำแหน่งของข้อมูลโหนดถัดจากโหนด I (Next i) (3) ชื่อ j (Vi) และ (4) พอยน์เตอร์ที่ใช้ไปยังตำแหน่งของข้อมูลโหนดถัดจากโหนด j (Next j) โดยในโหนด Directory จะชี้ไปยัง Edge Information แต่ละตัว

เครดิต https://sites.google.com/site/graphg6/kraf-khux-1/kar-thaen-khorngsrang-khxmul-kraf

การเรียงลำดับข้อมูล(Sorting)

การเรียงข้อมูล (Sorting)

         การจัดเรียงลำดับข้อมูลในที่นี้ หมายถึง การจัดเรียงข้อมูลให้มีการเรียงลำดับตามคีย์ที่ต้องการ โดยจะทำการเรียงข้อมูลจากค่าที่น้อยไปมาก หรือเรียงข้อมูลจากมากไปน้อยก็ได้ เช่น รายนามผู้ใช้โทรศัพท์ในสมุดโทรศัพท์ ซึ่งจะทำการเรียงลำดับข้อมูลตามตัวอักษร ส่วนรายชื่อของนักศึกษา จะทำการเรียงลำดับข้อมูลตามรหัสประจำตัว เป็นต้น

         การจัดเรียงลำดับข้อมูลนี้ แม้ว่าจะทำให้เสียเวลาในการจัดเรียง แต่จะมีผลช่วยทำให้การจัดการข้อมูลบางอย่างได้สะดวกและรวดเร็วขึ้น เช่น การค้นหาข้อมูล ดังนั้นการจัดเรียงลำดับข้อมูลจึงเป็นงานที่สำคัญอีกอย่างหนึ่งในระบบงานคอมพิวเตอร์

ประเภทของการจัดเรียงลำดับข้อมูล

         การจัดเรียงลำดับข้อมูลในระบบคอมพิวเตอร์ สามารถแบ่งออกได้เป็น 2 ประเภทใหญ่ ๆ คือ

         1.       การจัดเรียงลำดับภายใน (Internal Sorting) เป็นการจัดเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำ โดยข้อมูลเหล่านี้จะถูกเก็บอยู่ในโครงสร้างข้อมูลแบบอาร์เรย์ หรือลิงค์ลิสท์ ข้อมูลที่ทำการเรียงลำดับมีขนาดเล็กหรือจำนวนไม่มาก ซึ่งหน่วยความจำสามารถจะอ่านข้อมูลทั้งหมดขึ้นมาบนหน่วยความจำ และสามารถทำงานต่าง ๆ บนหน่วยความจำได้โดยไม่ต้องอาศัยสื่อบันทึกข้อมูล เช่น ดิสก์ หรือ เทป มาช่วยในการทำงาน

         2.       การจัดเรียงลำดับภายนอก (External Sorting) เป็นการจัดเรียงลำดับข้อมูลที่เก็บอยู่ในสื่อบันทึกข้อมูล โดยทั่วไปข้อมูลที่บันทึกนี้ มักมีจำนวนมากจนไม่สามารถจะเก็บเอาไว้ในหน่วยความจำได้ทั้งหมด ต้องแบ่งออกเป็นส่วนย่อย ๆ แล้วจึงนำมาจัดเรียงในหน่วยความจำ จากนั้นจึงทำการบันทึกกลับลงไปในสื่อสำหรับบันทึกข้อมูลเป็นส่วน ๆ ต่อจากนั้นนำส่วนต่าง ๆ ที่จัดเรียงลำดับเรียบร้อยแล้วมาทำการรวมเข้าด้วยกัน (Merge) สำหรับการเรียงแบบภายนอกนั้น จะต้องคิดถึงเวลาที่สูญเสียไปอันเนื่องจากการถ่ายเทข้อมูลระหว่างเทปหรือดิสก์ กับหน่วยความจำหลักด้วย เวลาที่สุญเสียไปในการถ่ายเทข้อมูลระหว่างหน่วยความจำหลักกับเทป หรือดิสก์จะเป็นตัวระบุความดีเลวของแบบการคำนวณแบบเรียงภายนอก

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

วิธีการต่าง ๆ สำหรับการจัดเรียงลำดับข้อมูล

         วิธีการในการจัดเรียงลำดับข้อมูลภายใน ได้แก่

         1.       การจัดเรียงลำดับข้อมูลแบบ Bubble Sort

         2.       การจัดเรียงลำดับข้อมูลแบบ Selection Sort

         3.       การจัดเรียงลำดับข้อมูลแบบ Insertion Sort

         4.       การจัดเรียงลำดับข้อมูลแบบ Quick Sort

         5.       การจัดเรียงลำดับข้อมูลแบบ Shell Sort

         6.       การจัดเรียงลำดับข้อมูลแบบ Heap Sort

         7.       การจัดเรียงลำดับข้อมูลแบบ Radix Sort

         วิธีการในการจัดเรียงลำดับข้อมูลภายนอก ได้แก่

         1.       การจัดเรียงลำดับข้อมูลแบบ Merge Sort

         2.       การ Run List

         3.       การเรียงข้อมูลบนดิสก์

         4.       การเรียงข้อมูลบนเทป

การจัดเรียงข้อมูลแบบ Bubble Sort

         เป็นวิธีการจัดเรียงลำดับข้อมูลด้วยการเปรียบเทียบคีย์ในตำแหน่งที่อยู่ติดกันทีละคู่ ถ้าคีย์ที่เปรียบเทียบไม่อยู่ในตำแหน่งที่ต้องการแล้วให้ทำการสลับที่กันระหว่างข้อมูล 2 ตัวนั้น ทิศทางการทำงานอาจจะทำจากคู่ซ้ายไปขวา หรือคู่ขวาไปซ้าย หรือคู่บนลงล่าง หรือคู่ล่างขึ้นบน ก็ได้

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

Unsorted	รอบที่  1  เปรียบเทียบทั้งหมด  9  ครั้ง	รอบที่  2  เปรียบเทียบทั้งหมด  8  ครั้ง
36	36      36      36      36      36      36      36      36     5	5        5        5        5        5        5        5        5
27	27      27      27      27      27      27      27      5       36	36      36     36       36      36      36      36      9
23	23      23      23      23      23      23      5       27      27	27      27     27      27      27      27       9       36
33	33      33      33      33      33      5       23      23      23	23      23     23      23      23      9       27       27
32	32      32      32      32      5       33      33      33      33	33     33      33      33      9        33      33      33
18	18      18      18      5       32       32     32      32      32	32      32      32      9       33      33     33       33
5	5        5        5       18      18       18      18      18     18	18      18      9       32      32      32      32       32
13	13      9       9        9         9        9        9        9        9	9        9       18       9       32       32      32      32
9	9       13      13      13       13      13      13     13      13	10      10     10      10     10        10      10     10
10	10     10      10      10       10      10      10     10      10	13      13     13      13     13        13      13     13

List  2	รอบที่  3  เปรียบเทียบ  7  ครั้ง			รอบที่  4  เปรียบเทียบ  6  ครั้ง				รอบที่  5  =  5  ครั้ง
5	5        5        5        5        5        5        5			5        5        5        5        5        5				5        5        5        5        5
9	9        9        9        9        9        9        9			9        9        9        9        9        9				9        9        9        9        9
36	36      36     36       36      36    36      10			10      10      10      10     10      10				10      10      10      10     10
27	27      27     27      27      27     10      36			36      36     36       36      36     13				13      13      13     13      13
23	23      23     23      23      10     27      27			27      27     27       27      13     36				36      36     36      36      18
33	33      33      33     10      23     23      23			23     23      23      13       27     27				27      27     27      18     36
32	32      32      10      33      33    33      33			33     33     13       23      23      23				23     23     18      2 7     27
18	18      10       32     32      32    32      32			32               13      33      33      33      33				33     18      23     23      23
10	10      18       18     18      18    18      18			13     32     32      32      32       32				18     33      33     33      33
13	13      13       13     13      13    13      13			18     18      18    18       18       18				32     32      32     32      32
List  5		รอบที่  6  =  4   ครั้ง	รอบที่  7  =  3		8   =  2	9  =  1
5		5        5        5        5	5        5        5		5        5	5
9		9        9        9        9	9        9        9		9        9	9
10		10      10      10      10	10      10      10		10      10	10
13		13      13       13     13	13      13       13		13      13	13
18		18     18       18     18	18     18      18		18     18	18
36		36     36       36      23	23     23      23		23     23	23
27		27     27       23      36	36     27      27		27     27	27
23		23     23       27      27	27     36      36		36     32	32
33		32     32       32     32	32     32      32		32     36	33
32		33      33    33      33	33      33    33		33      33	36

         จะเห็นได้ว่าข้อมูลมีการสลับที่กันไปเรื่อย ๆ  จนได้ข้อมูลที่มีการเรียงลำดับเป็นที่เรียบร้อยแล้ว  ซึ่งมีการจัดเรียง  n  -   1  รอบ  โดยในแต่ละรอบจะมีการเปรียบเทียบคีย์เป็น   n  -  1,  n  -  2,  n  -  3,….,3 ,2,1  ดังนั้น  จำนวนการเปรียบเทียบทั้งหมดจะเป็น

         1+2+3+…+(n  -  2)  +  (n  -  1)                                     =              n(n  -  1)/2

                                                                                                =              (n ²  -  n)/2

         จากตัวอย่างเมื่อแทนในสูตรจะได้                             =              (10 ²  -  10)/2

                                                                                                =              (100  -  10)/2

                                                                                                =              90/2

                                                                                                =              45

Algorithm  BUBBLE

         เพื่อใช้ในการจัดเรียงข้อมูลในอาร์เรย์  A  จากน้อยไปหามาก  โดยที่

                N             แทน        จำนวนข้อมูลทั้งหมด

                I               แทน        ตัวแปรนับรอบ

                J              แทน        ตัวแปรนับรอบ

                TEMP     แทน        ตัวแปรสำรองเพื่อเก็บค่าข้อมูล

1.               [ทำสิ่งต่อไปนี้ซ้ำ ๆ  จนถึงข้อ  3.  โดยที่ตัวแปร  I  เริ่มจาก  2  จนถึง  N  โดยเพิ่มค่าขึ้นครั้งละ  1]

REPEAT  THRU  STEP  3.  FOR  I  =  2  TO  N  STEP  1

2.               [ทำสิ่งต่อไปนี้ซ้ำ ๆ  จนถึงข้อ  3.  โดยที่ตัวแปร  J  เริ่มจาก  N  จนถึง  I  โดยลดค่าลงครั้งละ  1]

REPEAT  THRU  STEP  3.  FOR  J  =  N  TO  I  STEP  -1

3.               [เปรียบเทียบข้อมูล]

IF  A[J]  <  A[J-1]  THEN

        TEMP  =  A[J] 

        A[J]  =  A[J-1]

        A[J-1]  =  TEMP

ENDIF

4.               [จบการทำงาน]

EXIT

การจัดเรียงข้อมูลแบบ  Selection  Sort

         การจัดเรียงข้อมูลวิธีการนี้เป็นวิธีการที่ง่ายที่สุด  โดยเริ่มจาก 

1.               เลือกค่าของข้อมูลที่มีค่าน้อยที่สุด

2.               นำมาแลกเปลี่ยนกับค่าในตำแหน่งแรกสุดของกลุ่ม  A(1)

       หลังจากนั้นก็กระทำตามหลักการทั้ง  2  กับข้อมูลที่เหลือ  คือในครั้งที่  2  ค่า  A(2)  จะถูกแลกเปลี่ยนกับค่าที่เลือกแล้ว

ว่าน้อยที่สุดในลิสท์  A(2)…A(N)  และในครั้งที่  3  ค่า  A(3)  จะถูกแลกเปลี่ยนกับค่าที่เลือกแล้วว่าน้อยที่สุดในลิสท์  A(3)…A(N)  และเรื่อยไปจนกระทั่งเหลือข้อมูลที่จะเปรียบเทียบแค่  2  ค่าคือ  A(N-1)  และ  A(N)  ดังนั้น  จำนวนรอบในการกระทำเป็น  n-1  รอบ

ข้อมูลเดิม	44	33	11	55	77	90	40	60	99	22	88	66
I  =  1	44	33	11	55	77	90	40	60	99	22	88	66
I  =  2	11	33	44	55	77	90	40	60	99	22	88	66
I  =  3	11	22	44	55	77	90	40	60	99	33	88	66
I  =  4	11	22	33	55	77	90	40	60	99	44	88	66
I  =  5	11	22	33	40	77	90	50	60	99	44	88	66
I  =  6	11	22	33	40	44	90	55	60	99	77	88	66
I  =  7	11	22	33	40	44	55	90	60	99	77	88	66
I  =  8	11	22	33	40	44	55	60	90	99	77	88	66
I  =  9	11	22	33	40	44	55	60	66	99	77	88	90
I  =  10	11	22	33	40	44	55	60	66	77	99	88	90
I  =  11	11	22	33	40	44	55	60	66	77	88	99	90
I  =  12	11	22	33	40	44	55	60	66	77	88	90	90

Algorithm  SELECTION

         เพื่อใช้ในการจัดเรียงข้อมูลในอาร์เรย์  A  จากน้อยไปหามาก  โดยที่

                N             แทน        จำนวนข้อมูลทั้งหมด

                I               แทน        ตัวแปรนับรอบ

                J              แทน        ตัวแปรนับรอบ

                MIN        แทน        ตัวแปรที่เก็บตำแหน่งของข้อมูลที่มีค่าที่น้อยที่สุด

                TEMP     แทน        ตัวแปรสำรองเพื่อเก็บค่าข้อมูล

1.               [ทำสิ่งต่อไปนี้ซ้ำ ๆ  จนถึงข้อ  5.   โดยที่ตัวแปร  I  เริ่มจาก  จนถึง  N-1  โดยเพิ่มค่าขึ้นครั้งละ  1]

REPEAT  THRU  STEP  5.  FOR  I  =  1  TO  N-1  STEP  1

2.               [กำหนดค่าเริ่มต้นให้ตัวแปร  MIN  โดยให้]

MIN  =  I

3.               [ทำสิ่งต่อไปนี้ซ้า ๆ  จนถึงข้อ  4.  โดยที่ตัวแปร  J  เริ่มจาก  I  +  1  จนถึง  N  โดยเพิ่มค่าขึ้นค่าลงครั้งละ]

REPEAT  THRU  STEP  4.  FOR  J  =  I  +  1  TO  N  STEP  1

4.               [เปรียบเทียบข้อมูล]

IF  A[J]  <  A[MIN]  THEN

        MIN  =  J

ENDIF

5.               [ทำการสลับตำแหน่งของข้อมูลตัวที่มีค่าน้อยที่สุด  กับตัวปัจจุบัน]

TEMP =  A[I]

A[I]  =  A[MIN] 

A[MIN]  =  TEMP

6.               [จบการทำงาน]

EXIT

         การเรียงลำดับข้อมูลแบบ  Selection  Sort  มีการจัดเรียงทั้งหมด   n  -  1  รอบ  โดยในแต่ละรอบจะมีการเปรียบเทียบคีย์  ดังนี้

         รอบที่  1        จำนวนการเปรียบเทียบทั้งหมดจะเป็น               n  -  1  ครั้ง

         รอบที่  2        จำนวนการเปรียบเทียบทั้งหมดจะเป็น               n  -  2  ครั้ง

         รอบที่  3        จำนวนการเปรียบเทียบทั้งหมดจะเป็น               n  -  3  ครั้ง

                                                                .

                                                                .

                                                                .

         รอบที่  n  -  2                จำนวนการเปรียบเทียบทั้งหมดจะเป็น  2  ครั้ง

         รอบที่  n  -  1                จำนวนการเปรียบเทียบทั้งหมดจะเป็น  1  ครั้ง

         ดังนั้น  จำนวนการเปรียบเทียบทั้งหมดจะเป็น

         1+2+3+…+(n-2)+(n-1                  =  n(n-1)/2

                                                                =  (n ²  - n)/2