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

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

การใช้รายการประชิดมีข้อดีตรงที่ประหยัดพื้นที่มากกว่าการใช้แมตริกซ์ประชิด (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)
+ผลลัพธ์VertexNeighbors vertexABBACDCBDDBC

กราฟแบบมีทิศทาง (Directed graph)
+ผลลัพธ์VertexNeighbors vertexABACCBDAB

 ขั้นตอนวิธี (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)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 resultfrom 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