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

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

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

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

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

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

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

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

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

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

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

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

```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
```


## อ้างอิง

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