รายการประชิด

**รายการประชิด** () เป็นวิธีการของโครงสร้างแบบรายการของทฤษฎีกราฟ ซึ่งเป็นการใช้ลิสต์ในการเก็บข้อมูลของกราฟซึ่งเป็นโครงสร้างข้อมูลโดยวิธีการนี้จะใช้สำหรับการแก้ปัญหาของทฤษฎีกราฟ

การใช้รายการประชิดมีข้อดีตรงที่ประหยัดพื้นที่มากกว่าการใช้แมตริกซ์ประชิด (adjacency matrix) โดยเฉพาะเมื่อจำนวนเส้นเชื่อม (edges) มีน้อยเมื่อเทียบกับจำนวนโหนด การเข้าถึงเส้นเชื่อมทั้งหมดของโหนดใดโหนดหนึ่งสามารถทำได้อย่างมีประสิทธิภาพ เหมาะสำหรับอัลกอริทึมที่ต้องการสำรวจโหนดที่อยู่ติดกัน เช่น อัลกอริทึมการค้นหาแบบกว้าง (BFS) และลึก (DFS)

## ลักษณะการทำงาน

#### หลักการทำงาน
การทำงานของ Adjacency List สามารถแบ่งลักษณะการเก็บข้อมูลได้ 2 แบบตามการจำแนกชนิดของกราฟ คือ กราฟแบบมีทิศทาง (directed graph) และ กราฟแบบไม่มีทิศทาง (undirected graph) โดยสามารถใช้อัลกอริทึม การค้นหาแบบจำกัดความลึก(อังกฤษ : Depth-first Traversal) และ การค้นหาในแนวกว้าง(อังกฤษ : Breath-first Traversal) เพื่อค้นหาจุดที่เชื่อมต่อกันของกราฟ

ขั้นตอนการทำงานของรายการประชิด(Adjacency List)

* กำหนดให้ Vertex หมายถึง โหนด
* กำหนดให้ Edge หมายถึง เส้นเชื่อมของโหนด
* เพิ่มข้อมูล Vertex และ Edge เข้ามาในโปรแกรม
* ทำการวน Vertex และ Edge เพื่อสร้างทรัยขึ้นมา โดยใช้หลักการของลิงลิสต์
* เช็ค Vertex แต่ละตัวว่า Edge เชื่อมต่อกันหรือไม่

#### ตัวอย่างของกราฟไม่มีทิศทางและมีทิศทาง
กราฟไม่มีทิศทาง (Undirected graph)
left|thumb|182x182px|ตัวอย่างกราฟไม่มีทิศทาง

กราฟแบบมีทิศทาง (Directed graph)
left|thumb|ตัวอย่างกราฟแบบมีทิศทาง

## ขั้นตอนวิธี (Code)

### ขั้นตอนโค้ด
class Vertex(โหนด):

def รับข้อมูล(n)

กำหนดชื่อของ Vertex จากข้อมูลที่ได้รับ n

กำหนดลิสต์ของ Vertex

def เพิ่ม Vertex จากข้อมูล(v)

if ไม่มี Vertex ในลิสต์ของ Vertex

เพิ่ม Vertex จากฟังก์ชันรับข้อมูล เข้าไปในลิสต์

จัดเรียง Vertex ที่อยู่ในลิสต์

class Graph(กราฟ):

กำหนดลิสต์ของ Vertex ใหม่

def เพิ่ม Vertex(v)

if Vertex มาจากคลาส Vertex และ Vertex ที่มาจากคลาส Vertex ไม่อยู่ในลิสต์ของ Vertex ใหม่

กำหนด Vertex ตัวแรก

รีเทิร์น True

else:

รีเทิร์น False

def เพิ่ม Edge(u,v)

if u อยู่ใน Vertex ใหม่ และ v อยู่ใน Vertex ใหม่

Vertex ใหม่ u = ฟังก์ชันเพิ่ม Vertex จากข้อมูล v

Vertex ใหม่ v = ฟังก์ชันเพิ่ม Vertex จากข้อมูล u

รีเทิร์น True

else:

รีเทิร์น False

def รีเทิร์นผลลัพธ์

กำหนดลิสต์ของผลลัพธ์

for key in ลิสต์ของ Vertex ใหม่ที่ key

เพิ่มเข้าไปในลิสต์ของผลลัพธ์

รีเทิร์น ลิสต์ของผลลัพธ์

### ตัวอย่างโค้ด(Code)
เขียนโดย ภาษาไพทอน(Python)
```python3
class Vertex:
    def __init__(self, n):
        self.name = n
        self.neighbors = list()

    def add_neighbor(self, v):
        if v not in self.neighbors:
            self.neighbors.append(v)
            self.neighbors.sort()


class Graph:
    vertices = {}

    def add_vertex(self, vertex):
        if isinstance(vertex, Vertex) and vertex.name not in self.vertices:
            self.vertices[vertex.name] = vertex
            return True
        else:
            return False

    def add_edge(self, u, v):
        if u in self.vertices and v in self.vertices:
            self.vertices[u].add_neighbor(v)
            self.vertices[v].add_neighbor(u)
            return True
        else:
            return False

    def print_graph(self):
        res = []
        for key in sorted(list(self.vertices.keys())):
            res.append(key + str(self.vertices[key].neighbors))
        return res
```


### ตัวอย่างเทสเคส(Test case)
เขียนโดย ภาษาไพทอน(Python)

Scinario1: Graph have 5 vertex is A, B, C, D and E

Given list of vertex edge is ["AB","BC","CD",DE","EA"]

When convert vertex list to list of result

Then return list of result
```python3
from AdjencencyList import*

def test_adjencency_list_1():
	g = Graph()
	for i in range(ord('A'), ord('F')):
		g.add_vertex(Vertex(chr(i)))

	edges = ['AB', 'BC', 'CD', 'DE', 'EA']
	for edge in edges:
		g.add_edge(edge[:1], edge[1:])

	result = ["A['B', 'E']", "B['A', 'C']", "C['B', 'D']", "D['C', 'E']", "E['A', 'D']"]
	assert g.print_graph() == result
```


## ความเร็วในการทำงาน

### Big O
จากตัวอย่างโค้ดด้านบน Big(O) ของคลาส Vertex คือ O(n) + O(n) = O(2n) = O(n) = O(1)และ Big(O) ของคลาส Graph คือ O(n) + O(n) + O(n) = O(3n) = O(n)

#### Best case
คือ คลาส Vertex เนื่องจากต้องมีการทำงานทุกครั้งที่ใส่ข้อมูลเข้าไป จึงมีความเร็วในการทำงานเป็น O(1)

#### Worst case
คือ คลาส Graph เนื่องจากต้องมีการทำงานทุกครั้งที่รับข้อมูลจากคลาส Vertex จึงมีความเร็วในการทำงานเป็น O(n)

## อ้างอิง

greeksofgreeks. Graph and its representations. Retrieved 5 May 2018

youtube.mycodeschool. Graph Representation part 03 - Adjacency List(Oct 24, 2016).Retrieved 2 May 2018

youtube.Joe Jame.Python Link List(Jan 9, 2018).Retrieved 4 May 2018