โครงสร้างข้อมูลกราฟ · 2017-08-31 ·...

1

Charter 11

โครงสรางขอมลกราฟ Graphs

โครงสรางขอมลกราฟ (Graphs)

ความหมาย โครงสรางขอมลกราฟ (Graphs) เปนโครงสรางทไมเปนแบบรายการเชงเสน (Non-linear) กราฟเปนโครงสรางขอมลประเภทหนงทแสดงความสมพนธระหวาง vertex และ edge กราฟจะประกอบดวยกลมของ vertex ซงแสดงในกราฟดวยสญลกษณรปวงกลม และ กลมของ edge (เสนเชอมระหวาง vertex) ใชแสดงถงความสมพนธระหวาง vertex หากม vertex ตงแต 2 vertex ขนไปมความสมพนธกน ใชสญลกษณเสนตรงซงอาจมหวลกศร หรอไมมกได หรอกลาวอกลกษณะหนงวา กราฟ คอ เซตของจด (points) และเซตของเสน (lines) ซงเสนจะเปนตวเชอมโยงจากจดหนงไปยงอกจดหนง โดยเรยกจดเหลานวาโหนดของกราฟ (nodes of graph) และเรยกเสนวาดาน (edges)

2

Definition ! กราฟ G ประกอบดวยเซตจ ำกด 2 คอเซต V และ เซต E 1. เซต V = {v1, v2,…, vn} ทมสมำชก v1, v2,…, vn เรยกวำ จดยอด (vertices หรอ nodes)! 2. เซต E = {e1, e2,…, em} ทมสมำชก e1, e2,…, em เรยกวำ ดาน (edges) โดยทดำน e = (vi,vj) แตละดำนในเซต E ตรงกบ คทไมเปนอนดบ (vi,vj) = (vj,vi) ของจดยอดในเซต V เรำเขยนแทนกรำฟ G ดวย G = (V,E)

Graphs in Mathematics!

• Directed edge (ขอบมทศทาง) • เขยนดวยคอนดบ () • เชน a flight

• Undirected edge (ขอบไมมทศทาง) • เขยนดวยคทไมเปนอนดบ () • เชน a flight route

• Directed graph (กราฟระบทศทาง) • ทกขอบในกราฟเปน ขอบระบทศทาง • เชน route network

• Undirected graph (กราฟไมระบทศทาง) • ทกขอบในกราฟเปน ขอบไมระบทศทาง • เชน flight network

ชนดของขอบ(Edge Types)

ORD PVD

ORD PVD

Flight AA126

849 miles

5

ตวอยางของกราฟ


6

ก ำหนดให VG คอ เซตของโหนดในกรำฟ G EG คอ เซตของดำนในกรำฟ G สำมำรถเขยนแทนควำมหมำยของกรำฟไดดงน VG = { a, b, c, d } EG = { 1, 2, 3, 4, 5, 6, 7, 8 }


ในบำงครงกำรเชอมตอระหวำงโหนดสองโหนดใด ๆ อำจมดำนเชอม ตอไดหลำย ๆ ดำน ซงตำงกท ำใหเกดกำรเชอมโยงตอระหวำงโหนดสองโหนด ส ำหรบบำงโหนดอำจจะไมมกำรเชอมโยงใด ๆ เกดขน และบำงดำนกเชอมกบ โหนดเดม ซงจะเรยกดำนทเกดขนในลกษณะนวำลป (loops)

7

LOOP


• เสนทางการคมนาคม Transportation networks • Highway network • Flight network

Applications

Applications

• เครอขายคอมพวเตอร Computer networks • Local area network • Internet • Web

ค าศพทตาง ๆ ในกราฟ •End vertices (จดยอดปลำย) (or endpoints) of an edge

• U and V are the endpoints of a •Edges incident (ตกกระทบ) on a vertex

• a, d, and b are incident on V •Adjacent (ประชด) vertices

• U and V are adjacent •Degree (ดกร) of a vertex

• X has degree 5 •Parallel edges (ดำนขนำน)

• h and i are parallel edges •Self-loop (ลป)

• j is a self-loop

ค าศพทตาง ๆ ในกราฟ •Path (ทำงเดน)

• ล ำดบของจดยอดและขอบ • เรมทจดยอด และจบทจดยอด

•Simple path (ทำงเดนอยำงงำย) • ทำงเดนทมจดยอดและขอบแตกตำงกน

ตวอยำง P1=(V,b,X,h,Z) เปนทำงเดนอยำงงำย P2=(U,c,W,e,X,g,Y,f,W,d,V) เปนทำงเดนแตไมใชทำงเดนอยำงงำย

ค าศพทตาง ๆ ในกราฟ •Cycle (วงจร)

• ทางเดนทมจดเรมและจดปลายเดยวกน • Simple cycle (วงจรอยำงงำย) • วงจรทมจดยอดและขอบแตกตางกน

ตวอยำง C1=(V,b,X,g,Y,f,W,c,U,a,V) เปนวงจรอยำงงำย C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) เปนวงจรแตไมเปน วงจรอยำงงำย

กราฟจะเรยกวา กราฟอยางงาย (Simple Graph) ถามคณลกษณะตอไปน 1. กราฟตองไมมลป (Loops) 2. โหนดแตละคจะตองมดานไมเกน 1 ดาน

13

กราฟอยางงาย (Simple Graph)


แบงออกเปน 2 ประเภท ไดแก 1. กราฟไมมทศทาง (Undirected Graphs) 2. กราฟมทศทาง (Directed Graphs)

14

ประเภทของกราฟ


15

คอ กราฟทมดาน (Edges) ของกราฟจะไมมลกศรแสดงทศทางความ สมพนธทเกดขน (มองความสมพนธไดทงสองดาน)

กราฟไมมทศทาง (Undirected Graphs)

กราฟไมมทศทาง (Undirected Graphs)


16

คอ กราฟทมดาน (Edges) ของกราฟมลกศรแสดงทศทางความสมพนธ ทเกดขน

กราฟมทศทาง (Directed Graphs)

กราฟมทศทาง (Directed Graphs)


การแทนโครงสรางขอมลกราฟ คอ การแทนความสมพนธทเกดขนจากรปกราฟดวยรปทสามารถประมวลผลดวยคอมพวเตอร ซงแบงออกเปน 2 วธ ไดแก 1. การแทนดวย Adjacency Matrix 2. การแทนดวย Node Directory

17


18

การแทนดวย Adjacency Matrix

• เมตรกซประชด เปนวธกำรแทนกรำฟโดยจดเกบขอมลดวยโครงสรำงแบบ Matrix • Implement โดยใชโครงสรำง Array 2 มต • กำรเกบขอมลใน Adjacency Matrix ม 2 แบบคอ 1. กรณ Unweighted Graph ใหก ำหนดคำทเกบดงน ถำม edge (v,w) ให A[v,w] = 19 ถำไมม edge (v,w) ให A[v,w] = 09 2. กรณ Weighted Graph ใหก ำหนดคำทเกบดงน ถำม edge (v,w) ให A[v,w] = weight ถำไมม edge (v,w) ให A[v,w] = 09

19

I j 1 2 3 4 5 6

1 0 1 0 0 0 02 1 1 1 0 0 03 0 1 0 1 1 14 0 0 1 0 0 05 0 0 1 0 0 06 0 0 1 0 0 0

การแทน Undirected Graphs ดวย Adjacency Matrix


20

I j 1 2 3 4 5 6

1 0 1 0 0 0 02 0 1 1 0 0 03 0 0 0 0 1 14 0 0 1 0 0 05 0 0 0 0 0 06 0 0 0 0 0 0

การแทน Directed Graphs ดวย Adjacency Matrix


การแทนโครงสรางขอมลกราฟดวย Linked List การแทนดวย Linked List จะเกบขอมลเฉพาะโหนดทมความสมพนธกน (โหนดทไมเปนศนย) เทานน ซงท าใหประหยดเนอทไดมากกวาการแทนกราฟดวยอารเรย การแทนกราฟดวย Linked List แบงออกเปน 2 รปแบบ ไดแก 1. การแทนดวย Node Directory ประกอบดวย 2 สวน คอ

- Node Directory - Edge Information

2. การแทนกราฟแสดงดวยวธ Multi-List

21


การแทนโครงสรางขอมลกราฟดวย Linked List

22


• ลสตประชด เปนวธกำรแทนกรำฟโดยจดเกบขอมลดวยโครงสรำงแบบ Singly Linked List

• ประกอบดวยลสตของจดยอด และลสตของขอบ • กำรเกบขอมลใน Adjacency list ม 2 แบบ คอ

1.กรณ Unweighted Graph ใหก ำหนดคำทเกบ ดงน • ถำม edge (v,w) ให Pointer ของ v ชไปยง w • ถำไมม edge (v,w) ให Pointer ของ v ชไปยง Null

2. กรณ Weighted Graph ใหก ำหนดคำทเกบ ดงน • ถำม weight บน edge (v,w) ให Pointer ของ v ชไปยง w และเกบ

ขอมล weight ดวย

23

การแทนดวย Linked List


24

การแทน Undirected Graphs ดวยวธ Node Directory

การแทนดวย Node Directory


25

การแทน Directed Graphs ดวยวธ Node Directory

การแทนดวย Node Directory


26

การแทนดวย Multi List

เมอ Vi หมายถง โหนด i Vj หมายถง โหนด j NEXTi หมายถง พอยนเตอรทชไปยงโหนดทอยถดจากโหนด Vi ทท าใหเกดดาน NEXTj หมายถง พอยนเตอรทชไปยงโหนดทอยถดจากโหนด Vj ทท าใหเกดดาน


27

แสดงเซตของดำนดวย Multi List

การแทนดวย Multi List


กราฟทม Weighted Edges

คอ กราฟทมขอมลก ากบอยบนดานของกราฟ โดยขอมลดงกลาวอาจจะหมายถงระยะทาง จ านวนวนหรอจ านวนเงน เปนตน ทงนขนอยกบความสมพนธของกราฟนนแทนความหมายของสงใด เชน ตวอยางแผนทแสดงระยะทางระหวางเมองตาง ๆ

28


29

ตวอยางกราฟทม Weighted Edges แสดงระยะทางระหวางเมองตาง ๆ


การด าเนนงานของกราฟ (Graph Operations)

• กำรแทรกเวอรเทกซ (Insert Vertex) • กำรลบเวอรเทกซ (Delete Vertex) • กำรเพมเอดจ(Add Edge) • กำรลบเอดจ (Delete Edge) • กำรคนหำเวอรเทกซ (Find Vertex) • กำรทองเขำไปในกรำฟ (Traverse Graph)


การแทรกเวอรเทกซ (Insert Vertex)


การลบเวอรเทกซ (Delete Vertex)


การเพมเอดจ (Add Edge)


การลบเอดจ (Add Edge)


การคนหาเวอรเทกซ (Find Vertex)


การทองเขาไปในกราฟ (Traverse Graph) • กำรทองเขำไปในกรำฟแบบแนวลก (Depth-First Search :

DFS) • กำรทองเขำไปในกรำฟแบบแนวกวำง (Breadth-First Search

:BFS) • กำรทองเขำไปในกรำฟแบบล ำดบควำมส ำคญ (Priority First

Search :PFS)


การทองเขาไปในกราฟ (Traverse Graph) • การทองเขาไปในกราฟแบบแนวลก (Depth-First Search)

เปนลกษณะกำรทองเขำไปยงโหนดเรมตน แลวใหโหนดใกลเคยงเปนโหนดเรมตน เขำเยยมโหนดท ำตอไปจนกระทงไมมโหนดใกลเคยงจงยอนกลบมำยงโหนดกอนหนำ และเขำเยยมโหนดอกดำนดวยรปแบบเดยวกนจนครบ เทยบไดกบกำรทองเขำไปในทรแบบพรออเดอร

1.Push vertex 2.Pop vertex และประมวลผล 3.Push adjacent ทงหมดของ Vertex ในขอ 2 4.ท ำซ ำขอ2-3จนกวำจะครบทก Vertex และ Stack วำง


การทองเขาไปในกราฟ (Traverse Graph) • การทองเขาไปในกราฟแบบแนวลก (Depth-First Search)

เปนกำรทองเขำไปในกรำฟโดยเขำเยยมโหนดตวแรกและด ำเนนกำร หำกมโหนดใกลเคยงจะด ำเนนกำรกบโหนดทอยดำนซำยกอน 1.Enqueue vertex 2.Dequeue vertex และประมวลผล 3.Enqueue adjacent ทงหมดของ Vertex ในขอ 2 4.ท ำซ ำขอ 2-3 จนกวำจะครบทก Vertex และ Queue วำง


การทองเขาไปในกราฟ (Traverse Graph) • การทองเขาไปในกราฟแบบแนวกวาง (Breath-First Search)


การทองเขาไปในกราฟ (Traverse Graph) • การทองเขาไปในกราฟแบบแนวกวาง (Breath-First Search)


การทองเขาไปในกราฟ (Traverse Graph) • การทองเขาไปในกราฟแบบแนวล าดบความส าคญ (Priority-First

Search)

มรปแบบของกำรทองเขำไปเยยม (Visit) โหนดตำงๆ ดวยรปแบบของควทมล ำดบควำมส ำคญ (Priority Queues) แทนทโครงสรำงสแตกหรอควแบบทวไป คอ กำรเพมควเขำมำโดยพจำรณำและด ำเนนกำรในล ำดบทส ำคญกอน


กรำฟประกอบดวยโหนดเวอรเทกซ (Vertex) และเซตของเสนเชอมระหวำงเวอรเทกซหรอเอดจ (Edge) เสนเชอมระหวำงเวอรเทกซทงแบบมทศทำง (Directed edge) กรำฟเสนเชอมไมมทศทำงแนนอน เรยกวำกรำฟแบบไมมทศทำง (Undirected edge) และโครงสรำงกรำฟมทงเสนเชอมแบบมทศทำง และเสเชอมแบบไมมทศทำง เรยกวำ กรำฟผสม (Mixed Graph) ซงบำงครงกมเสนเชอมเชอมระหวำงโหนด 2 โหนดใดๆ มำกกวำ 1 กำรส ำรวจตำมแนวกวำง (Breadth-first) กำรส ำรวจตำมแนวลก (Depth-first) และกำรส ำรวจตำมล ำดบ (Priority-first)

โอภำส เอยมสรวงศ โครงสรำงขอมล (Data Structures) เพอกำรออกแบบโปรแกรมคอมพวเตอร.—กรงเทพฯ:ซเอดยเคชน,2549.

Reference :

โครงสร้างข้อมูลกราฟ · 2017-08-31 ·...

Documents