เมตริกซ์ประชิด

แมทริกซ์ประชิด (อังกฤษ: adjacency matrix) จะใช้เวกเตอร์ (อาร์เรย์หนึ่งมิติ) เพื่อจัดเก็บเวอร์เท็กซ์และใช้แมทริกซ์(อาร์เรย์สองมิติ) เพื่อจัดเก็บเอดจ์ ถ้าหากเวอร์เท็ฏซ์คู่หนึ่งอยู่ประชิดกันและมีเอดจ์เชื่อมโยงระหว่างเวอร์เท็กซ์คู่นั้น แมทริกคู่นั้นจะมีค่าเป็น 1 ในขณะที่หากไม่มีเอดจ์เชื่อมโยงนั่นหมายถึงไม่มีเส้นทางระหว่างกัน แมทริกคู่นั้นก็จะถูกกำหนดให้ มีค่าเท่ากับ 0 ในกรณีเป็นกราฟแบบมีทิศทางหรือไดกราฟ แมทริกซ์ประชิดจะมีลูกศรเป็นตัวกำหนดทิศทาง

การแทนที่กราฟด้วยเมตริกซ์

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

กราฟระบุทิศทาง

รูปที่ 2

จากรูปที่ 2 หากนำมาแทนที่ด้วยเมตริกซ์จะแทนที่ได้ด้วยจำนวน n x n ซึ่ง n ก็คือ A,B,C,D,E,F เป็น 6 จำนวน โหนดทำให้ได้ค่าเมตริกซ์ จำนวน 6 x 6 = 36 ช่อง และเมื่อพิจารณาตามทิศทางของการเชื่อมต่อ หากโหนดใดมีเส้นเชื่อมต่อไปยังโหนดอื่นให้ระบุตัวเลขลงไปในเมตริกซ์เป็น 1 แต่ถ้าโหนดใดไม่ได้มีการระบุว่าทำการเชื่อมต่อก็ให้ระบุเป็น 0 ดังรูปภาพที่ 3

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

พิจารณาโหนด A มีเส้นเชื่อมต่อระบุไป B ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

พิจารณาโหนด B มีเส้นเชื่อมต่อระบุไป C, E ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

รูปที่ 3

พิจารณาโหนด C มีเส้นเชื่อมต่อระบุไป D, E ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

พิจารณาโหนด D ไม่มีเส้นเชื่อมต่อระบุไปยังโหนดอื่นระบุหมายเลข 0 ทุกช่อง

พิจารณาโหนด E มีเส้นเชื่อมต่อระบุไป D, F ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0

พิจารณาโหนด F ไม่มีเส้นเชื่อมต่อระบุไปยังโหนดอื่นระบุหมายเลข 0 ทุกช่อง

กราฟไม่ระบุทิศทาง

รูปที่ 4

จากรูปภาพที่ 4 กราฟแบบไม่ระบุทิศทางเมื่อนำมาแทนที่ด้วยเมตริกซ์สามารถที่จะกำหนดจำนวนช่องได้เช่นเดียวกับไดกราฟ คือ n x nและระบุตัวเลขสำหรับการเชื่อมต่อ คือ 1 และ 0 แต่ในการวางตำแหน่งโหนดในแนวนอน และแนวตั้งนั้น ระบุเป็นโหนดต้นทางและโหนดปลายทางได้ในตัวเดียวกัน ในรูปภาพที่ 5

จากรูปที่ 5 เป็นการกำหนดเขียนเลขกำกับเมตริกซ์โดยอ่านค่าทั้งแนวตั้งและแนวนอน เช่น

โหนด A มีเส้นเชื่อมต่อ ที่ระบุไปยังโหนด B ได้และเช่นกันโหนด Bสามารถที่จะเชื่อมต่อมายังโหนด A ได้ จึงระบุตัวเลขในเมตริกซ์เป็น1

โหนด B มีเส้นเชื่อมต่อ A, C, E ได้ระบุเป็น 1 และ A, C, E ระบุช่องโหนด B เป็น 1 เช่นกัน โหนด C มีเส้นเชื่อมต่อ B, D, E ได้ระบุเป็น 1 และ B, D, E ระบุช่องโหนด C เป็น 1 เช่นกัน

โหนด D มีเส้นเชื่อมต่อ C, E ได้ระบุเป็น 1 และ C, E ระบุช่องโหนด Dเป็น 1 เช่นกัน

รูปที่ 5

โหนด E มีเส้นเชื่อมต่อ B, C, D, F ได้ระบุเป็น 1 และ B, C, D, F ระบุช่องโหนด ฎ เป็น 1 เช่นกัน

โหนด F มีเส้นเชื่อมต่อ E ได้ระบุเป็น 1 และ E ระบุช่องโหนด F เป็น 1 เช่นกัน

กรณีที่กราฟมีการวนลูป(Loop)

ในกรณีที่ีกราฟมีการวนลูป ในภาพที่ 6 จะแทนค่าตำแหน่งที่มีการวนลูปเป็นเลข 2

รูปที่ 6

การจัดเก็บโครงสร้างกราฟด้วย Adjacency Matrix

วิธีการอย่างง่ายในการจัดเก็บโครงสร้างกราฟ คือ อาร์เรย์สองมิติที่เก็บความสัมพันธ์ระหว่างจุดยอดใกล้เคียงในกราฟ เรียกว่า แอดจาเซนซีเมตริกซ์ (Adjacency Matrix) โดยหากกราฟประกอบด้วยจุดยอด ${\displaystyle v_{1},v_{2},v_{3},...,v_{n}}$ จะสามารถแสดงกราฟในรูปของแอดจาเซนซีเมตริกซ์ X ขนาด n x n โดย ${\displaystyle x_{ij}=1}$ ในกรณีมีเส้นเชื่อมระหว่างจุดยอด ${\displaystyle v_{i}}$และ ${\displaystyle v_{j}}$ และ ${\displaystyle x_{ij}=0}$ ในกรณีไม่มีเส้นเชื่อมระหว่างจุดยอด ${\displaystyle v_{i}}$ และ ${\displaystyle v_{j}}$ และ ${\displaystyle i,j\leqslant n}$

รูป (ข) แสดงการจัดเก็บโครงสร้างกราฟแบบไม่มีทิศทางของกราฟในรูป (ก) โดยแถวที่ 1 ของอาร์เรย์ X แสดงการเชื่อมโยงจากจุดยอด a ไปยังจุดยอดอื่นๆ ที่เป็นจุดยอดใกล้เคียง เช่น จุดยอด a เชื่อมโยงไปยังจุดยอด b c และ d ดังนั้น ค่า ${\displaystyle x_{12}x_{13}}$และ ${\displaystyle x_{14}}$จะมีค่าเป็น 1 ส่วนแถวที่ 2-4 แสดงการเชื่อมโยงจากจุดยอด b c หรือ d ไปยังจุดยอดอิ่นๆ ตามลำดับ ซึ่งการแทนกราฟแบบไม่มีทิศทาง ลักษณะของอาร์เรย์สองมิติที่ได้จะมีลักษณะสมมาตร (Symmetric) เรียกว่า เมทริกซ์ทแยงมุม (Diagonal Matrix) นั่นคือ ค่าของ ${\displaystyle x_{ij}=x_{ji}}$ ซึ่งเป็นค่าที่แสดงความสัมพันธ์ระหว่างจุดยอด i และจุดยอด j ว่ามีเส้นเชื่อมโยงถึงกัน ดังนั้น จำนวนช่อง ${\displaystyle x_{ij}}$ ที่มีค่าเท่ากับ 1 จะเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ แต่หากเป็นกราฟแบบมีทิศทาง จำนวนช่อง ${\displaystyle x_{ij}}$ ที่มีค่าเท่ากับ 1 จะเท่ากับจำนวนเส้นเชื่อมในกราฟ เช่น ${\displaystyle x_{14}}$ และ ${\displaystyle x_{41}}$จะเก็บค่า 1 หมายถึงมีเส้นเชื่อมโยงระหว่างจุดยอด a และจุดยอด d นั่นเอง

ตัวอย่างโค้ดในภาษา python

class Graph(object): def __init__(self, edge_list): self.edge_list = edge_list def add_edge(self, edge_list): self.edge_list.append(edge_list) def adj_mtx_diect(self): v = 0 counter = set() for src, dest in self.edge_list: counter.add(src) counter.add(dest) v = len(counter) mtx = [[0 for y in range(v)]for x in range(v)] for e in self.edge_list: src, dest = e src = src - 1 dest = dest - 1 if src == dest: mtx[src][dest] = 2 else: mtx[src][dest] = 1 return mtx def adj_mtx_undiect(self): v = 0 counter = set() for src, dest in self.edge_list: counter.add(src) counter.add(dest) v = len(counter) mtx = [[0 for y in range(v)]for x in range(v)] for e in self.edge_list: src, dest = e src = src - 1 dest = dest - 1 if src == dest: mtx[src][dest] = 2 mtx[dest][src] = 2 else: mtx[src][dest] = 1 mtx[dest][src] = 1 return mtx 

อ้างอิง

1. . คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2018-05-20. สืบค้นเมื่อ 2018-05-12.
2. รูปที่ 1 https://www.slideshare.net/tumetr/graph-43943214
3. http://piyapan-aod.blogspot.com/2009/03/graph.html
4. https://stackoverflow.com/questions/29464252/adjacency-matrix-in-python
5. https://algocoding.wordpress.com/2014/08/24/adjacency-list-representation-of-a-graph-python-java/
6. https://pythonandr.com/tag/adjacency-matrix/
7. . คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2018-05-15. สืบค้นเมื่อ 2018-05-13.
8. http://www.cs.science.cmu.ac.th:88/course/204251/lib/exe/fetch.php?media=graph.pdf^[]