รายการประชิด
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
รายการประชิด (อังกฤษ: adjacency list) เป็นวิธีการของโครงสร้างแบบรายการของทฤษฎีกราฟ ซึ่งเป็นการใช้ลิสต์ในการเก็บข้อมูลของกราฟซึ่งเป็นโครงสร้างข้อมูลโดยวิธีการนี้จะใช้สำหรับการแก้ปัญหาของทฤษฎีกราฟ
ลักษณะการทำงาน
หลักการทำงาน
การทำงานของ 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)
| Vertex | Neighbors vertex | ||
|---|---|---|---|
| A | B | ||
| B | A | C | D |
| C | B | D | |
| D | B | C | |
กราฟแบบมีทิศทาง (Directed graph)
| Vertex | Neighbors vertex | ||
|---|---|---|---|
| A | |||
| B | A | C | |
| C | B | ||
| D | A | B | |
ขั้นตอนวิธี(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)
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)
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
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