Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
รายการประชิด (อังกฤษ: 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
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud raykarprachid xngkvs adjacency list epnwithikarkhxngokhrngsrangaebbraykarkhxngthvsdikraf sungepnkarichlistinkarekbkhxmulkhxngkrafsungepnokhrngsrangkhxmulodywithikarnicaichsahrbkaraekpyhakhxngthvsdikraflksnakarthanganhlkkarthangan karthangankhxng Adjacency List samarthaebnglksnakarekbkhxmulid 2 aebbtamkarcaaenkchnidkhxngkraf khux krafaebbmithisthang directed graph aela krafaebbimmithisthang undirected graph odysamarthichxlkxrithum karkhnhaaebbcakdkhwamluk xngkvs Depth first Traversal aela karkhnhainaenwkwang xngkvs Breath first Traversal ephuxkhnhacudthiechuxmtxknkhxngkraf khntxnkarthangankhxngraykarprachid Adjacency List kahndih Vertex hmaythung ohnd kahndih Edge hmaythung esnechuxmkhxngohnd ephimkhxmul Vertex aela Edge ekhamainopraekrm thakarwn Vertex aela Edge ephuxsrangthrykhunma odyichhlkkarkhxnglinglist echkh Vertex aetlatwwa Edge echuxmtxknhruximtwxyangkhxngkrafimmithisthangaelamithisthang krafimmithisthang Undirected graph twxyangkrafimmithisthangphllphth Vertex Neighbors vertexA BB A C DC B DD B C krafaebbmithisthang Directed graph twxyangkrafaebbmithisthangphllphth Vertex Neighbors vertexAB A CC BD A Bkhntxnwithi Code khntxnokhd class Vertex ohnd def rbkhxmul n kahndchuxkhxng Vertex cakkhxmulthiidrb n kahndlistkhxng Vertex def ephim Vertex cakkhxmul v if immi Vertex inlistkhxng Vertex ephim Vertex cakfngkchnrbkhxmul ekhaipinlist cderiyng Vertex thixyuinlist class Graph kraf kahndlistkhxng Vertex ihm def ephim Vertex v if Vertex macakkhlas Vertex aela Vertex thimacakkhlas Vertex imxyuinlistkhxng Vertex ihm kahnd Vertex twaerk riethirn True else riethirn False def ephim Edge u v if u xyuin Vertex ihm aela v xyuin Vertex ihm Vertex ihm u fngkchnephim Vertex cakkhxmul v Vertex ihm v fngkchnephim Vertex cakkhxmul u riethirn True else riethirn False def riethirnphllphth kahndlistkhxngphllphth for key in listkhxng Vertex ihmthi key ephimekhaipinlistkhxngphllphth riethirn listkhxngphllphth twxyangokhd Code ekhiynody phasaiphthxn 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 twxyangethsekhs Test case ekhiynody phasaiphthxn 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 resultkhwamerwinkarthanganBig O caktwxyangokhddanbn Big O khxngkhlas Vertex khux O n O n O 2n O n O 1 aela Big O khxngkhlas Graph khux O n O n O n O 3n O n Best case khux khlas Vertex enuxngcaktxngmikarthanganthukkhrngthiiskhxmulekhaip cungmikhwamerwinkarthanganepn O 1 Worst case khux khlas Graph enuxngcaktxngmikarthanganthukkhrngthirbkhxmulcakkhlas Vertex cungmikhwamerwinkarthanganepn O n xangxinggreeksofgreeks 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