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

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

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

 กราฟระบุทิศทาง 
จากรูปที่ 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 
พิจารณาโหนด C มีเส้นเชื่อมต่อระบุไป D, E ระบุหมายเลข 1 นอกนั้นระบุค่าเป็น 0 

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

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

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

 กราฟไม่ระบุทิศทาง 
จากรูปภาพที่ 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 เช่นกัน 
โหนด E มีเส้นเชื่อมต่อ B, C, D, F ได้ระบุเป็น 1 และ B, C, D, F ระบุช่องโหนด ฎ เป็น 1 เช่นกัน 

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

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

 การจัดเก็บโครงสร้างกราฟด้วย Adjacency Matrix 
วิธีการอย่างง่ายในการจัดเก็บโครงสร้างกราฟ คือ อาร์เรย์สองมิติที่เก็บความสัมพันธ์ระหว่างจุดยอดใกล้เคียงในกราฟ เรียกว่า แอดจาเซนซีเมตริกซ์ (Adjacency Matrix) โดยหากกราฟประกอบด้วยจุดยอด   จะสามารถแสดงกราฟในรูปของแอดจาเซนซีเมตริกซ์ X ขนาด  n x n โดย  ในกรณีมีเส้นเชื่อมระหว่างจุดยอด  และ  และ  ในกรณีไม่มีเส้นเชื่อมระหว่างจุดยอด  และ  และ  
รูป (ข) แสดงการจัดเก็บโครงสร้างกราฟแบบไม่มีทิศทางของกราฟในรูป (ก) โดยแถวที่ 1 ของอาร์เรย์ X แสดงการเชื่อมโยงจากจุดยอด a ไปยังจุดยอดอื่น ๆ ที่เป็นจุดยอดใกล้เคียง เช่น จุดยอด a เชื่อมโยงไปยังจุดยอด b c และ d ดังนั้น ค่า และ จะมีค่าเป็น 1 ส่วนแถวที่ 2-4 แสดงการเชื่อมโยงจากจุดยอด b c หรือ d ไปยังจุดยอดอื่น ๆ ตามลำดับ ซึ่งการแทนกราฟแบบไม่มีทิศทาง ลักษณะของอาร์เรย์สองมิติที่ได้จะมีลักษณะสมมาตร (Symmetric) เรียกว่า เมทริกซ์ทแยงมุม (Diagonal Matrix) นั่นคือ ค่าของ  ซึ่งเป็นค่าที่แสดงความสัมพันธ์ระหว่างจุดยอด i และจุดยอด j ว่ามีเส้นเชื่อมโยงถึงกัน ดังนั้น จำนวนช่อง  ที่มีค่าเท่ากับ 1 จะเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ แต่หากเป็นกราฟแบบมีทิศทาง จำนวนช่อง  ที่มีค่าเท่ากับ 1 จะเท่ากับจำนวนเส้นเชื่อมในกราฟ เช่น  และ จะเก็บค่า 1 หมายถึงมีเส้นเชื่อมโยงระหว่างจุดยอด a และจุดยอด d นั่นเองhttp://www.cs.science.cmu.ac.th:88/course/204251/lib/exe/fetch.php?media=graph.pdf

 ตัวอย่างโค้ดในภาษา 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

อ้างอิง

หมวดหมู่:โครงสร้างข้อมูลแบบกราฟ